dynamic programming
Senior Member
Contest hôm nay dễ quá làm đc 4 bài mà rank vẫn hơn 1kWeekly contest sáng nay có lộn bộ đề ko mà easy thế nhỉ
Sent from Samsung SM-G986U1 using vozFApp
Contest hôm nay dễ quá làm đc 4 bài mà rank vẫn hơn 1kWeekly contest sáng nay có lộn bộ đề ko mà easy thế nhỉ
Sent from Samsung SM-G986U1 using vozFApp
Contest hôm nay dễ quá làm đc 4 bài mà rank vẫn hơn 1k
Công nhận bài hnay khó thật, trước từng làm qua rồi mà h làm lại vẫn thấy chua
Không hiểu sao mình thấy bài hard hôm nay dễ hơn bài medium hôm qua. Khá straightforward để tìm quy tắc QHĐ, không lắt léo gì.
Cách nghĩ của bài này là:
- với dãy có 1, 2, .., n-1,
- Thử thêm n vào thì sẽ có n vị trí khác nhau,
- Trừ vị trí cuối thì tất cả các vị trí còn lại đều tăng số Inverse Pair vì n lớn hơn tất cả các số có sẵn trong dãy,
- Từ đó dễ suy ra công thức QHĐ: T(n, k) = T(n-1, k) + T(n-1, k-1) + ... + T(n-1, k-n+1).
Cái bước thử chèn n vào là khá tự nhiên, còn những phần còn lại chỉ là tính toán + / - cơ bản.
Sent from HUAWEI DBY-W09 using vozFApp
Thế này là do trình bác cao hơn 2 ông bên trên rồi.
nó chỉ rank theo thời gian submit đc accept thôi chứ ko care cách làm có tối ưu hay ko thím nhỉ
Sent from Samsung SM-G986U1 using vozFApp
Không hiểu sao mình thấy bài hard hôm nay dễ hơn bài medium hôm qua. Khá straightforward để tìm quy tắc QHĐ, không lắt léo gì.
Cách nghĩ của bài này là:
- với dãy có 1, 2, .., n-1,
- Thử thêm n vào thì sẽ có n vị trí khác nhau,
- Trừ vị trí cuối thì tất cả các vị trí còn lại đều tăng số Inverse Pair vì n lớn hơn tất cả các số có sẵn trong dãy,
- Từ đó dễ suy ra công thức QHĐ: T(n, k) = T(n-1, k) + T(n-1, k-1) + ... + T(n-1, k-n+1).
Cái bước thử chèn n vào là khá tự nhiên, còn những phần còn lại chỉ là tính toán + / - cơ bản.
Sent from HUAWEI DBY-W09 using vozFApp
Thím dùng @cache của python à ? Vì cái này cái hashmap lớn quá nên bị chậm đó. Thím đổi lại dùng memo tay = array là được.e cũng nghĩ ra công thức qhđ ntn nhưng mà vẫn dính TLE ko biết optimize thế nào
Sent from Samsung SM-G986U1 using vozFApp
Thím dùng @cache của python à ? Vì cái này cái hashmap lớn quá nên bị chậm đó. Thím đổi lại dùng memo tay = array là được.
Edit: Vẫn hong được, thôi dùng bottom up cho dễ ông giáo ạ
class Solution:
def kInversePairs(self, n: int, k: int) -> int:
# ## Top-down
# @lru_cache(None)
# def dp(n,k):
# if n==0:
# return 0
# if k==0:
# return 1
# res=0
# for i in range(min(k,n-1)+1):
# res+=dp(n-1,k-i)
# return res
# return dp(n,k)
## Bottom-up: convert recursion to iterative
dp=[[0]*(k+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(k+1):
if j==0:
dp[i][j]=1
else:
for t in range(min(j,i-1)+1):
dp[i][j]+=dp[i-1][j-t]
return dp[-1][-1]
Bottom up đây vẫn TLE bác ơi
Cách này độ phức tạp vẫn là O(n*k*min(n,k)). Bài này tag hard nên nó chỉ accept O(n*k) thôi
Spoil thế. Huhu. Bài này tui nghĩ sáng h mất 30p còn chưa ra ý tưởng nào18 / 7 / 2022:
_ Tạo mảng 2d sum sao cho sum[i.][j.] là tổng của submatrix có điểm đầu (0, 0) và điểm cuối (i, j)
- 1 câu hard khá quen thuộc
- Đề bài yêu cầu tìm 1 submatrix có tổng bằng target -> nghĩ ngay tới two sum
- Ý tưởng dễ nhất: gọi điểm đầu submatrix là (x1, y1) và điểm cuối là (x2, y2)
-> cần 4 vòng for cho mỗi biến x1, y1, x2, y2
- Tính toàn bộ sum -> time O(n^2)
- tại mỗi submatrix có điểm đầu (x1, y1) và điểm cuối (x2, y2) có tổng = sum[x2.][y2.] - sum[x1 - 1][y2] - sum[x2.][y1 - 1] + sum[x1 - 1][y1 - 1]
-> ra đáp án
-> ra đáp án
- Time O(n ^ 4)
- Code: https://leetcode.com/submissions/detail/749851671/
- đến đây có thể tối ưu giống bài two sum
- chỉ cần 3 biến x, y1, y2 và tạo 1 hash map
- chọn 2 điểm y1, y2 bất kì thuộc khoảng (1 -> n)
- chạy biến x từ 1-> m
- ở mỗi lần x, map[tổng submatrix có điểm đầu (0, y1) và điểm cuối (x, y2)]++;
- result += map[tổng submatrix trên - target];
- Time: O(n^3)
- Code: https://leetcode.com/submissions/detail/749875299/
- Câu khá quen, làm chắc tầm 20p
// std::array<std::array<int, 128>, 128> sum{};
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
// find
int res = 0;
// std::unordered_map<int, int> count{};
for (int r1 = -1; r1 < m-1; ++r1) {
std::array<int, 101> sum{0};
for (int r2 = r1 + 1; r2 < m; ++r2) {
// count.clear();
// count[0] = 1;
int prev = 0;
for (int c2 = 0; c2 < n; ++c2) {
int old = sum[c2+1];
int nnew = (sum[c2+1] += sum[c2] - prev + matrix[r2][c2]);
prev = old;
res += std::count(&sum[0], &sum[c2+1], nnew - target);
// if (auto it = count.find(nnew-target); it != count.end()) {
// res += it->second;
// }
// ++count[nnew];
}
}
}
return res;
}
};
auto _ = []() {
std::cin.sync_with_stdio(false);
std::cin.tie(0);
return 0;
}();
Bác nói chuẩn quá em làm cách O(mmn) nhanh hơn được 5%Bài hôm nay kích thước có 100 nên dùng cách O(n^4) nhanh hơn O(n^3) hash map.
View attachment 1271205
https://leetcode.com/submissions/detail/749963010/
C++:// std::array<std::array<int, 128>, 128> sum{}; class Solution { public: int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); // find int res = 0; // std::unordered_map<int, int> count{}; for (int r1 = -1; r1 < m-1; ++r1) { std::array<int, 101> sum{0}; for (int r2 = r1 + 1; r2 < m; ++r2) { // count.clear(); // count[0] = 1; int prev = 0; for (int c2 = 0; c2 < n; ++c2) { int old = sum[c2+1]; int nnew = (sum[c2+1] += sum[c2] - prev + matrix[r2][c2]); prev = old; res += std::count(&sum[0], &sum[c2+1], nnew - target); // if (auto it = count.find(nnew-target); it != count.end()) { // res += it->second; // } // ++count[nnew]; } } } return res; } }; auto _ = []() { std::cin.sync_with_stdio(false); std::cin.tie(0); return 0; }();
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows <= 0:
return []
output = [[1]]
for i in range(2, numRows + 1):
row = [1]
for j in range(1, i-1):
row.append(output[-1][j-1] + output[-1][j])
row.append(1)
output.append(row)
return output
Python mà nhiều chữ thế ct.Sau 2 ngày ra bài Hard loạn hết cả não thì hnay đc thư giãn một hôm . Đen vâu keep it real, code theo kiểu đơn giản nhất:
Code:class Solution: def generate(self, numRows: int) -> List[List[int]]: if numRows <= 0: return [] output = [[1]] for i in range(2, numRows + 1): row = [1] for j in range(1, i-1): row.append(output[-1][j-1] + output[-1][j]) row.append(1) output.append(row) return output