freedom.9
Senior Member
Mình còn cùi lắm fence, nay ăn hên thôi nhưng mà cũng có tiến bộ vl rồi mừng quákhông cần template là tư duy giải bài của anh tốt đó, chứ chưa chi đã nghĩ ngay dùng template như em cũng không tốt lắm
Mình còn cùi lắm fence, nay ăn hên thôi nhưng mà cũng có tiến bộ vl rồi mừng quákhông cần template là tư duy giải bài của anh tốt đó, chứ chưa chi đã nghĩ ngay dùng template như em cũng không tốt lắm
T cũng vừa làm xong, lần đầu làm được 4 câuView attachment 2362398
Hardwork must be paid off các fence ơi lần đầu giải được 4 bài mừng quá hahahaha
Bài cuối để print nó ghi output limit exceed đm leetcode sida làm bug 1 phát cmnr
Ăn mừng thôi mai fenceT cũng vừa làm xong, lần đầu làm được 4 câu
View attachment 2362438
sorted list của bác là cái này à? sortedlist libBài cuối mình dùng sortedlist + với binary search nên ko cần template gì, thấy còn dễ hơn cả bài 3 kaka.
Đúng rồi bácsorted list của bác là cái này à? sortedlist lib
Mấy bài matrix ko làm nhiều dễ loạn lắm.Gần 1 năm mới quay trở lại leetcode contest.
Q2 gang rồi các bác ạ
Bài đó em brute force bị LTE.Mấy bài matrix ko làm nhiều dễ loạn lắm.
Q2 mình xài dp đó fence
var countSubmatrices = function(g, k) {
const e = [];
let c = 0
for (let i = 0; i < g.length; i++) {
const row = Array(g[0].length).fill(0);
e.push(row);
}
let s1 = 0
for(let i = 0; i < g.length; i++){
s1 += g[i][0]
e[i][0] = s1
if(s1 <= k){
c++
}
}
let s2 = 0
for(let i = 0; i < g[0].length; i++){
s2 += g[0][i]
e[0][i] = s2
if(s2 <= k && i !== 0){
c++
}
}
for(let i = 1; i < g.length; i++){
for(let j = 1; j < g[0].length; j++){
e[i][j] = e[i-1][j] + e[i][j-1] - e[i-1][j-1] + g[i][j]
if(e[i][j] <= k){
c++
}
}
}
return c;
};
Bài 2 của mình đây, công thức là sum(i,j)= sum(i-1, j) + sum (i, j - 1) - sum (i - 1, j -1)Bài đó em brute force bị LTE.
Sau đó phải tìm cách tính linh ta linh tinh, vẫn được accept ( em không biết gì về khái niệm DP hay các cái giải thuật, trước giờ toàn làm theo cảm tính )
var countSubmatrices = function(g, k) { const e = []; let c = 0 for (let i = 0; i < g.length; i++) { const row = Array(g[0].length).fill(0); e.push(row); } let s1 = 0 for(let i = 0; i < g.length; i++){ s1 += g[i][0] e[i][0] = s1 if(s1 <= k){ c++ } } let s2 = 0 for(let i = 0; i < g[0].length; i++){ s2 += g[0][i] e[0][i] = s2 if(s2 <= k && i !== 0){ c++ } } for(let i = 1; i < g.length; i++){ for(let j = 1; j < g[0].length; j++){ e[i][j] = e[i-1][j] + e[i][j-1] - e[i-1][j-1] + g[i][j] if(e[i][j] <= k){ c++ } } } return c; };
class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
m = len(grid)
n = len(grid[0])
if grid[0][0] > k:
return 0
ans = 0
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
ans += 1
dp[0][0] = grid[0][0]
else:
x = y = 0
if j - 1 < 0:
x = 0
else:
x = dp[i][j - 1]
if i - 1 < 0:
y = 0
else:
y = dp[i- 1][j]
sum = x + y
if i - 1 >= 0 and j - 1 >= 0:
sum -= dp[i-1][j - 1]
dp[i][j] = grid[i][j] + sum
if dp[i][j] <= k:
ans +=1
return ans
class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
m = len(grid)
n = len(grid[0])
if grid[0][0] > k:
return 0
ans = 0
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
prefixSum = 0
for j in range(n):
prefixSum += grid[i][j]
dp[i][j] = prefixSum
if i - 1 >= 0:
dp[i][j] += dp[i - 1][j]
if dp[i][j] <= k:
ans +=1
return ans
Thằng đứng đầu hình như là wiliam Lin có kênh Youtube à, làm nhanh hơn thời gian tôi đọc đề nữaView attachment 2362398
Hardwork must be paid off các fence ơi lần đầu giải được 4 bài mừng quá hahahaha
Bài cuối để print nó ghi output limit exceed đm leetcode sida làm bug 1 phát cmnr
Mình nghĩ là sẽ có rejudge. Cho testcase một dãy giảm 10^5 phần tử là những solution time complexity O(n^2) sẽ bị TLE thôi.Đm weak testcases q4 nữa rồi, hi vọng tụi nó rejudge đừng cancel.
Mấy thằng C++ giải On^2 vẫn pass
via theNEXTvoz for iPhone
Top8, cao thủ phương nào đâyflashmt - LeetCode Profile
View flashmt's profile on LeetCode, the world's largest programming community.leetcode.com
via theNEXTvoz for iPhone
Missing Test Case - 3072. Distribute Elements Into Two Arrays II · Issue #20947 · LeetCode-Feedback/LeetCode-Feedback (https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/20947#issuecomment-1976890913)Mình nghĩ là sẽ có rejudge. Cho testcase một dãy giảm 10^5 phần tử là những solution time complexity O(n^2) sẽ bị TLE thôi.
Nhưng mình nghĩ phải cho một dãy 2* 10^5 phần tử thì mới chắc ăn quét hết solution O(n^2).
Kì ta, có thể tụi leetcode nó add testcases để rejudge rồi. Để mai chờ xem kết quả evaluation như nào.Missing Test Case - 3072. Distribute Elements Into Two Arrays II · Issue #20947 · LeetCode-Feedback/LeetCode-Feedback (https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/20947#issuecomment-1976890913)
Có một leetcoder gửi testcase lên để quét solution Time Complexity: O(n^2) mà bị từ chối.