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ồikhô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ừng quá 
thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
mừng quá 
ilovely
Member
T cũng vừa làm xong, lần đầu làm được 4 câuXem tệp đính kèm 2362398
Hardwork must be paid off các fence ơilầ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
freedom.9
Senior Member
Ăn mừng thôi mai fence
trinity
Senior Member
sorted list của bác là cái này à? sortedlist lib
freedom.9
Senior Member
Đúng rồi bác
freedom.9
Senior Member
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 ạ
Q2 mình xài dp đó fence
youknowwho151
Member
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;
};
freedom.9
Senior Member
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; };
Cái này có thể apply cho bài toán tìm sum của 1 square bất kì trong matrix được luôn, đợt gần đây thấy meta với google hay cho bài toán tính sum của 1 square bất kì trong matrix
Python:
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
Python:
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
Sửa lần cuối:
RTX3090
Senior Member
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ữaXem tệp đính kèm 2362398
Hardwork must be paid off các fence ơi
Bài cuối để print nó ghi output limit exceed đm leetcode sida
freedom.9
Senior Member
Đ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
Mấy thằng C++ giải On^2 vẫn pass
via theNEXTvoz for iPhone
humanversion9x
Senior Member
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
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).
hieunm3538
Senior Member
Top8, cao thủ phương nào đây
flashmt - LeetCode Profile
View flashmt's profile on LeetCode, the world's largest programming community.leetcode.com
via theNEXTvoz for iPhone
Profile of Nguyen Tan Sy Nguyen - Competitive Programming Hall Of Fame
Competitive Programming Hall Of Fame
cphof.org
flashmt là tay to trong làm CP rồi bác, bạc HSG Tin quốc tế năm 2011 còn đi thi ACM ICPC WF năm 13 16 nữa mà
Vừa trâu vừa nhiều kinh nghiệm
humanversion9x
Senior Member
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.
freedom.9
Senior Member
Kì ta, có thể tụi leetcode nó add testcases để rejudge rồi. Để mai chờ xem kết quả evaluation như nào.
PhanNgocLong123
Senior Member
Noted. Đang ôn lại kiến thức để pv bigtech. Cuối tháng này join với mọi người.
freedom.9
Senior Member
- Trạng thái
Chủ đề tương tự
