thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
Kân team v3
Senior Member
toy edit ròi đấy, thím brinbt đưa bài hard dạng recover array tương tự. Thay vì double mỗi value trong array ban đầu như bài hôm nay thì bài hard này nó thêm a[.i]-k và a[.i]+k với k nguyên dương bất kì
Lập Trình Viên Số Khổ
Senior Member
à thảo nào cứ thấy có "k" gì ko bik
Kân team v3
Senior Member
lỡ 1 phần tử nó lập nhiều lần thì xao nên toy mới xài cái mapcái num max là 2000 phần tử, nên chỉ cần array<bool, 2001> là đủ, khỏi phải cấp phát động sau mỗi lần tìm k. Rồi dùng binary search thôi, do cái nums t đã sort rồi.
optimize code lại bỏ bớt mấy chỗ cấp phát động ko cần thiết cũng xuống được ~90ms ròi
thuyduong2007
Member
vậy mới cần xử lý khéo léo. Vd lần đầu search ra num[i ] + 2*k tại x. thì lần tiếp theo sẽ chỉ search num[i+1]+2*k trong khoảng [x+1,nums.end()) thôi,lỡ 1 phần tử nó lập nhiều lần thì xao nên toy mới xài cái map
optimize code lại bỏ bớt mấy chỗ cấp phát động ko cần thiết cũng xuống được ~90ms ròi
Kân team v3
Senior Member
dỏm kute chêvậy mới cần xử lý khéo léo. Vd lần đầu search ra num + 2*k tại x. thì lần tiếp theo sẽ chỉ search num[i+1]+2*k trong khoảng [x+1,nums.end()] thôi,
thuyduong2007
Member
vấn đề k nằm ở cái logN. Mà làm ntn k phải cấp phát động nhiều lần cho cái map/unordered_map + cache friendly nữa.dỏm kute chên ~chỉ cỡ 1k mà optimize cái tìm kiếm logn làm gì
Kân team v3
Senior Member
sửa lại trong cái flat map kia của toy cũng dễ, thêm cái offset hint là được mà giờ submit nó toàn 120ms, nãy ăn hên được 87msvấn đề k nằm ở cái logN. Mà làm ntn k phải cấp phát động nhiều lần cho cái map/unordered_map + cache friendly nữa.
thuyduong2007
Member
đc khoảng đó là hit the wall rồi. lâu lâu ăn hên thì đc cao, t ăn hên có 55 ms đây,sửa lại trong cái flat map kia của toy cũng dễ, thêm cái offset hint là được mà giờ submit nó toàn 120ms, nãy ăn hên được 87ms
.https://leetcode.com/submissions/detail/800499854/
Mà bài này thì t thấy cách của @bribnt là xịn rồi.
Kân team v3
Senior Member
toy optimize thuật toán O(n^2) mà nó toàn 140ms chắc thằng LC thấy toy submit nhiều quá nó cho chạy mấy con cpu dỏm ròi
edit đổi code này, thế
https://leetcode.com/submissions/detail/800600830/
edit đổi code này, thế
CustomIntQueue bằng std::queue<int> cũng được
Bài hôm nay hợp gu ghê 
Gọi n là số phần tử của nums, m là số phần tử của multipliers
Quy hoạch động, độ phức tạp là O(m*m) = O(10^6)
Gọi F(i, j) là giá trị lớn nhất có thể đạt được sau khi thực hiện i operation, và ta đã duyệt qua j phần tử đầu tiên của nums (và i-j phần tử cuối cùng của nums)
Gọi số phần tử ở dưới cuối của mảng nums mà ta đã duyệt qua là nR = i - j
F(i, j) = max (
F(i-1, j-1) + multipliers[i-1] * nums[j-1], // lấy phần tử bên trái
F(i-1, j) + multipliers[i-1] * nums[n-nR], // lấy phần tử bên phải
)
Kết quả trả về là max ( F(m, i) ) với i chạy từ 0 đến m
Quy hoạch động, độ phức tạp là O(m*m) = O(10^6)
Gọi F(i, j) là giá trị lớn nhất có thể đạt được sau khi thực hiện i operation, và ta đã duyệt qua j phần tử đầu tiên của nums (và i-j phần tử cuối cùng của nums)
Gọi số phần tử ở dưới cuối của mảng nums mà ta đã duyệt qua là nR = i - j
F(i, j) = max (
F(i-1, j-1) + multipliers[i-1] * nums[j-1], // lấy phần tử bên trái
F(i-1, j) + multipliers[i-1] * nums[n-nR], // lấy phần tử bên phải
)
Kết quả trả về là max ( F(m, i) ) với i chạy từ 0 đến m
Violet_7
Member
Lúc đầu làm space O(n) khá rối, sau thì phải chơi space O(n^2) ms hết rối. Mất 30p cho 1 câu medium 
.
Code: https://leetcode.com/submissions/detail/800879811/
.Code: https://leetcode.com/submissions/detail/800879811/
Kân team v3
Senior Member
qhd mà medium gì ko biết
đệ quy memoize TLE nghỉ chơi
https://leetcode.com/submissions/detail/800916001/
đổi cái cache từ
https://leetcode.com/submissions/detail/800921314/ LC chạy cái gì mà lúc thì 1100ms lúc thì 485ms dỏm thặc
https://leetcode.com/submissions/detail/800922338/ sửa lại cái này đẹp nhứt nhưng chạy 900ms submit mãi ko ra 500ms nữa
đệ quy memoize TLE nghỉ chơi
đổi cái cache từ
unordered_map thành mảng 2 chiều thì ok
https://leetcode.com/submissions/detail/800922338/ sửa lại cái này đẹp nhứt nhưng chạy 900ms submit mãi ko ra 500ms nữa
Sửa lần cuối:
thuyduong2007
Member
Bài này làm O(m*m) làm python dùng @cache là dính TLE liền, đổi qua C++ dùng mảng 2 chiều thay cho cái @cache thì mới pass. Trên python chắc phải đổi qua dùng mảng 2 chiều trong numpy mới pass đc,qhd mà medium gì ko biết
đệ quy memoize TLE nghỉ chơihttps://leetcode.com/submissions/detail/800916001/
đổi cái cache từunordered_mapthành mảng 2 chiều thì okhttps://leetcode.com/submissions/detail/800918725/
Kân team v3
Senior Member
python có cho chỉnh kiểu của @cache koBài này làm O(m*m) làm python dùng @cache là dính TLE liền, đổi qua C++ dùng mảng 2 chiều thay cho cái @cache thì mới pass. Trên python chắc phải đổi qua dùng mảng 2 chiều trong numpy mới pass đc,
Phải chơi 2 mảng dp cho left/right mới qua được.
O(m^2) time, O(n) space.
https://leetcode.com/submissions/detail/800925640/
O(m^2) time, O(n) space.
https://leetcode.com/submissions/detail/800925640/
thuyduong2007
Member
t thấy nó có input là user_function đó. Test thử xem thím kân,python có cho chỉnh kiểu của @cache ko
https://docs.python.org/3/library/functools.html
Kân team v3
Senior Member
t thấy nó có input là user_function đó. Test thử xem thím kân,
https://docs.python.org/3/library/functools.html
có đổi kiểu của cache được đâu, mặc định là dict ròi
thuyduong2007
Member
Tự viết cái cache thì chắc đc.có đổi kiểu của cache được đâu, mặc định là dict ròi
_Gia_Cat_Luong_
Senior Member
Ảo thật, cùng 1 code mà python TLE còn java chạy ra 92% :v
https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/submissions/
https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/submissions/
- Trạng thái
Chủ đề tương tự
