thảo luận Leetcode mỗi ngày

Giờ mới biết cách dùng deque, lúc sáng dùng multiset với priority_queue chậm quá toàn dưới 30%. Đổi sang cách này được 99% ngay.

Mình implement lại bằng circular buffer để giảm bộ nhớ từ O(n) -> O(k). Vì chỉ cần phải lưu tối đa k kết quả gần nhất.

https://leetcode.com/submissions/detail/742326916/
cái deque họ cũng chỉ lưu tối đa k kết quả gần nhất mà bác, thừa nó pop ra hết rùi
 
7/9/2022:
  • 1 câu medium khá quen
  • Ý tưởng là 1 câu biến tấu câu max window: https://leetcode.com/problems/sliding-window-maximum/
  • lời giải câu trên https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
  • tạo mảng dp với dp[i.] là max score khi con ếch đến ô thứ i
  • vì con ếch chỉ nhảy đc từ 1 đến k bước nên để đến đc ô thứ i thì trước đó con ếch có thể đứng ở 1 trong k ô trước đó
  • vậy nếu biết dp của k ô trước đó thì dp[i.] = max(dp[i - k] -> dp[i - 1]) + nums[i.]
  • như vậy áp dụng công thức qhđ trên và ý tưởng câu tìm max trên 1 đoạn tịnh tiến k sẽ ra đáp án
  • Lúc đầu cx áp dụng cái câu max window kia mà phức tạp xét âm dương nên code hơi dài, đọc solution thì chả cần phải tách âm dương làm j nên đã tối ưu code lại:
https://leetcode.com/submissions/detail/742162855/
bài khó vãi, bài lv hard là áp dụng slide trực tiếp trên dãy, bài này medium áp dụng slide trên mảng dp
 
Ý ông kia là cái dãy dp để lưu kết quả tạm ấy, k phải cái deque để xử lý phần tính max trên dp.
cái này nâng cao quá, mà đọc code C++ bác ý viết lần nào cũng bị váng đầu, nó trong code có mỗi cái buffer, ko cần cả mảng lưu DP và DEQUE, hơi khó hiểu :sad:,

à nó là dạng pair, chắc lưu cả 2 vào đấy, nhưng vẫn rất khó hiểu :beat_brick:
 

bribnt

Đã tốn tiền
Mà thuật toán này hay thật.
Nhìn qua thấy 2 vòng lặp lồng nhau tưởng là O(nk). Nhưng nếu phân tích kỹ hơn thì là O(n) vì cái dq chỉ được push và pop tối đa n lần.

Sent from Xiaomi M2007J20CG using vozFApp
 
Giờ mới biết cách dùng deque, lúc sáng dùng multiset với priority_queue chậm quá toàn dưới 30%. Đổi sang cách này được 99% ngay.

Mình implement lại bằng circular buffer để giảm bộ nhớ từ O(n) -> O(k). Vì chỉ cần phải lưu tối đa k kết quả gần nhất.

https://leetcode.com/submissions/detail/742326916/
Cao nhân đang làm bên mảng nào vậy? :big_smile: thấy code viết khá tricky và thường theo kiểu micro optimize.
 

Vô Danh Tử

Senior Member
a chị có thể recommend cho e 1 vài sách cơ bản của ctdl hay thuật toán đc k ạ. e mới thi đh xong muốn hè này học thêm ạ^^
 

dntt_00

Senior Member
https://leetcode.com/problems/subsets/
có thím nào cho em hỏi câu này em làm thế này cũng n2^n mà bị timeout nhỉ. :/
Python:
def subsets(nums):
    res = [[]]
    for i in range (1, 2**len(nums)):
        mask = 0
        list = []
        while mask < len(nums):
            if i & (1<<mask) != 0:
                list.append(nums[mask])
            mask = mask + 1
        res.append(list)
    return res
 
Last edited:
Giải thuật và lập trình của thầy Lê Minh Hoàng
Overrated
doubt-icon.png
 

Gâu Gâu Gâu Gâu

Senior Member
https://leetcode.com/problems/subsets/
có thím nào cho em hỏi câu này em làm thế này cũng n2^n mà bị timeout nhỉ. :/
Python:
def subsets(nums):
    res = [[]]
    for i in range (1, 2**len(nums)):
        mask = 0
        list = []
        while mask < len(nums):
            if i & (1<<mask) != 0:
                list.append(nums[mask])
            mask = mask + 1
        res.append(list)
    return res

mình paste vào python thì thấy chạy ngon.

Bài này mình dùng đệ quy đơn giản thôi thấy 100% :D cách thím giải nhìn lạ lạ hay hay, giải thích giúp mình đi :D Sao biết size của res là 2^n, tại sao lại i % (1 << mask) != 0
 

dntt_00

Senior Member
mình paste vào python thì thấy chạy ngon.

Bài này mình dùng đệ quy đơn giản thôi thấy 100% :D cách thím giải nhìn lạ lạ hay hay, giải thích giúp mình đi :D Sao biết size của res là 2^n, tại sao lại i % (1 << mask) != 0
à cái này mấy năm trước có đọc qua mấy bài dùng bitmask, giờ code thì ban đầu nhớ cái khái niệm tập hợp -> ra được 2^n tập con (kể cả tập rỗng), rồi tự dưng nhớ tới cái bitmask này, ngồi code lại :v, khi tạo tập con, phần tử được lấy -> 1, k được lấy -> 0, tương tự kiểu bit.
rồi phần còn lại là mình lặp qua 1 đến 2^n -1 rồi dùng bitmask để lấy index các phần tử sẽ lấy, cái % kia là phép & nha. ví dụ với i = 1, 2, 4, 8 -> tương ứng với các số nhị phân 01, 10, 100, 1000 -> thấy chỉ có 1 phần tử được chọn, tương ứng với các tập con có 1 phần tử, mấy cái còn lại tương tự.
lol em giải thích hơi lộn xộn, @@
còn cái thím nói chắc backtracking, nãy em có đọc solution, đầu em hay bị rối khi nghĩ mấy cái này lắm :(
 

_Gia_Cat_Luong_

Senior Member
Bài hôm nay kiểu như version easy của bài hqua, cố định k = 2. Code đơn giản:

Python:
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        a, b = 0, 0
        for n in cost:
            a, b = b, n + min(a, b)
            
        return min(a, b)
 

...Batman...

Senior Member
Bài hôm nay kiểu như version easy của bài hqua, cố định k = 2. Code đơn giản:

Python:
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        a, b = 0, 0
        for n in cost:
            a, b = b, n + min(a, b)
           
        return min(a, b)
Em cũng thấy hơi lừa với đề bài hôm nay.
trong C++ có cách nào lấy min, max 2 số nhanh hơn (a > b? a:b) ko nhỉ ?
BlKBCuN.png
 

kyo_pyro

Senior Member
Em cũng thấy hơi lừa với đề bài hôm nay.
trong C++ có cách nào lấy min, max 2 số nhanh hơn (a > b? a:b) ko nhỉ ?
BlKBCuN.png
Có std::min với std::max mà thím.

C++ không có trò return về 2 biến nên đành dùng mảng 2 phần tử :(
C++:
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (cost.size() == 2){
            return min(cost[0],cost[1]);
        }
        vector<int> recentCost{0,0};
        for (auto i = 2;i<=cost.size();i++){
            recentCost[i%2] = min(
                recentCost[i%2] + cost[i-2],
                recentCost[(i+1)%2] + cost[i-1]
            );
        }
        
        return recentCost[cost.size()%2];
    }
};
 

bribnt

Đã tốn tiền
Em cũng thấy hơi lừa với đề bài hôm nay.
trong C++ có cách nào lấy min, max 2 số nhanh hơn (a > b? a:b) ko nhỉ ?
BlKBCuN.png

Có nhé min(x, y) = y ^ ((x ^ y) & -(x < y))

Ưu điểm: không cần rẽ nhánh nên sẽ nhanh hơn if else trong trường hợp tổng quát.

Sent from Xiaomi M2007J20CG using vozFApp
 
Top