Thử suy nghĩ bth trước nếu k dùng DP thì fen sẽ giải ntn ?
. Tui có list các bài DP cho beginner, nếu fen cần thì hộp tui gửi cho.
tui đã hiểu đâu fen
, hiểu thì đã biết cách sửa giữa strict và loosely rồi, mới đang tìm code trên mạng thui, dần dần chắc mới hiểu sâu đượcclass Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> caches(nums.size(), 0);
int maxLen = 0;
for (int i = 0; i < nums.size(); i++){
int curVal = lengthOfLISRecursive(nums, caches, i);
maxLen = max(maxLen, curVal);
}
return maxLen;
}
int lengthOfLISRecursive(vector<int>& nums, vector<int> &caches, int pos) {
if (pos == nums.size() - 1) return 1;
if (caches[pos] > 0) return caches[pos];
int maxLen = 1;
for (int i = pos + 1; i < nums.size(); i++){
if (nums[i] <= nums[pos]) continue;
int curVal = 1 + lengthOfLISRecursive(nums, caches, i);
maxLen = max(maxLen, curVal);
}
caches[pos] = maxLen;
return maxLen;
}
};
sort rồi binary search
Nói rõ chỗ binary search ra được ko bác. Em chưa hiểu chỗ binary search thì sao mình tính tổng 3 con số được
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda i: i[1])
lastTime = -math.inf
count = 0
for start, end in intervals:
if start < lastTime:
count += 1
else:
lastTime = end
return countChắc ý thím này là sort, sau đó viết 2 vòng for để pick ra 2 số, số còn lại dùng binary search do dãy đã đc sort. Làm vậy thì độ phức tạp là O(n^2logn). Khả năng cao timeout.
Vậy giờ làm sao bác. Bác cho em gợi ý đi, để em vượt qua bài này với
O(n^2logn) thì cũng k khác mấy với O(n^2) nên chắc k timeout đâu fen. Nhưng bài này dùng hashmap có thể làm O(n^2). Bất lợi là tốn O(n) space.
Nếu bạn lặp với mỗi cặp số trong mảng (O(n^2)). Bạn sẽ có tổng a + b. Bài toán trở thành kiểm tra xem trong mảng có tồn tại số c sao cho a + b +c = target hay không. Bạn có thể tự nghĩ thêm làm sao để kiểm tra điều này, với gợi ý là dùng binary search (O(logn)) hoặc Hashmap (O(1)).
chạy i từ 0 đến n-3, j=i+1, k=n-1
nlogn thôi fen
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if nums == [0, 0, 0]:
return [[0, 0, 0]]
res = []
nums.sort()
ia = 0
while ia < len(nums) - 2:
ib = ia + 1
ic = len(nums) - 1
while ib < ic:
s = nums[ia] + nums[ib] + nums[ic]
if s < 0:
ib += 1
elif s > 0:
ic -= 1
else:
a, b, c = nums[ia], nums[ib], nums[ic]
while nums[ib] == b and ib < ic:
ib += 1
while nums[ic] == c and ib < ic:
ic -= 1
res.append([a, b, c])
a = nums[ia]
while ia < len(nums)-2 and nums[ia] == a:
ia += 1
return restrong wiki là nó giải bằng 2-pointer
sorrry fen, my bad
Chời ơi làm tui ngồi ngẫm nãy giờ, thấy k có phép chia nào mà chạy được O(nlogn) hay dữ dội vậy T_T.
bác giải bài 2sum bằng 2pointer chưa? Bài ấy O(n), bài này thêm 1 vòng for ngoài nữa là O(n^2), bài này em làm tuần trước, mấy tuần này bận thi cuối kì quá không code được. Mà e thấy mới làm leetcode 2 3 tuần học được đúng cái trò sort với 2pointer, học vững lý thuyết nhảy vào làm nhiều tác dụng hơn.
Trước đọc sách mấy bữa là làm ngon đệ qui, quay lui rồi
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
if(nums.size()==0) return res;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-1;++i){
if(i!=0 && nums[i]==nums[i-1]) continue;
int l= i+1;
int r= nums.size()-1;
while(l<r){
if(nums[i]+nums[l]+nums[r]==0){
res.push_back({nums[l],nums[i],nums[r]});
l++;
r--;
while(l<r&&nums[l]==nums[l-1])
l++;
}
else if(nums[i]+nums[l]+nums[r]<0){
l++;
}
else{
r--;
}
}
}
return res;
}
};
cài = segtree ăn TLE rồichưa thấy code lis = segment tree baoh
b implement thử bài pair cho mình xem với
cài bằng cây fenwick thì ăn được#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
typedef pair <int, int> ii;
vector<int> node[N], ft[N];
ii vA[N];
int n;
void update(vector<int> &ft, int pos, int val) {
for ( ; pos <= ft.size(); pos += (pos & -pos)) {
ft[pos] = max(ft[pos], val);
}
}
int get(vector<int> &ft, int pos) {
int ans = 0;
for ( ; pos > 0; pos -= (pos & -pos)) {
ans = max(ans, ft[pos]);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
vector<int> vX(n), vY(n);
for (int i = 1; i <= n; ++i) {
cin >> vX[i - 1] >> vY[i - 1];
vA[i] = {vX[i - 1], vY[i - 1]};
}
sort(vX.begin(), vX.end());
sort(vY.begin(), vY.end());
for (int i = 1; i <= n; ++i) {
vA[i].first = (int) (lower_bound(vX.begin(), vX.end(), vA[i].first) - vX.begin()) + 1;
vA[i].second = (int) (lower_bound(vY.begin(), vY.end(), vA[i].second) - vY.begin()) + 1;
// Fake GET
for (int j = vA[i].first - 1; j > 0; j -= (j & -j)) {
node[j].push_back(vA[i].second);
}
// FAke update
for (int j = vA[i].first; j <= n; j += (j & -j)) {
node[j].push_back(vA[i].second);
}
}
for (int i = 1; i <= n; ++i) {
node[i].push_back(10000032);
sort(node[i].begin(), node[i].end());
node[i].erase(unique(node[i].begin(), node[i].end()), node[i].end());
ft[i].resize(node[i].size() + 1, 0);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int x = vA[i].first, y = vA[i].second;
int tmp = 1;
for (int j = x - 1; j > 0; j -= (j & -j)) {
int currentY = (int) (lower_bound(node[j].begin(), node[j].end(), y) - node[j].begin()) + 1;
tmp = max(tmp, get(ft[j], currentY - 1) + 1);
}
for (int j = x; j <= n; j += (j & -j)) {
int currentY = (int) (lower_bound(node[j].begin(), node[j].end(), y) - node[j].begin()) + 1;
update(ft[j], currentY, tmp);
}
ans = max(ans, tmp);
/* cerr << tmp << '\n'; */
}
cout << ans << '\n';
return 0;
}Liệu có thể làm thế này k fen. LIS theo chiều thứ nhất trước, ra 1 mảng LIS con. Sau đó làm LIS theo chiều thứ 2 trên mảng con này => Ra kết quả.cài = segtree ăn TLE rồi
C++:#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 3; typedef pair <int, int> ii; vector<int> node[N], ft[N]; ii vA[N]; int n; void update(vector<int> &ft, int pos, int val) { for ( ; pos <= ft.size(); pos += (pos & -pos)) { ft[pos] = max(ft[pos], val); } } int get(vector<int> &ft, int pos) { int ans = 0; for ( ; pos > 0; pos -= (pos & -pos)) { ans = max(ans, ft[pos]); } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n; vector<int> vX(n), vY(n); for (int i = 1; i <= n; ++i) { cin >> vX[i - 1] >> vY[i - 1]; vA[i] = {vX[i - 1], vY[i - 1]}; } sort(vX.begin(), vX.end()); sort(vY.begin(), vY.end()); for (int i = 1; i <= n; ++i) { vA[i].first = (int) (lower_bound(vX.begin(), vX.end(), vA[i].first) - vX.begin()) + 1; vA[i].second = (int) (lower_bound(vY.begin(), vY.end(), vA[i].second) - vY.begin()) + 1; // Fake GET for (int j = vA[i].first - 1; j > 0; j -= (j & -j)) { node[j].push_back(vA[i].second); } // FAke update for (int j = vA[i].first; j <= n; j += (j & -j)) { node[j].push_back(vA[i].second); } } for (int i = 1; i <= n; ++i) { node[i].push_back(10000032); sort(node[i].begin(), node[i].end()); node[i].erase(unique(node[i].begin(), node[i].end()), node[i].end()); ft[i].resize(node[i].size() + 1, 0); } int ans = 0; for (int i = 1; i <= n; ++i) { int x = vA[i].first, y = vA[i].second; int tmp = 1; for (int j = x - 1; j > 0; j -= (j & -j)) { int currentY = (int) (lower_bound(node[j].begin(), node[j].end(), y) - node[j].begin()) + 1; tmp = max(tmp, get(ft[j], currentY - 1) + 1); } for (int j = x; j <= n; j += (j & -j)) { int currentY = (int) (lower_bound(node[j].begin(), node[j].end(), y) - node[j].begin()) + 1; update(ft[j], currentY, tmp); } ans = max(ans, tmp); /* cerr << tmp << '\n'; */ } cout << ans << '\n'; return 0; }
