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

Cố Trường Ca · 10/9/24

NotFunny đã nói:
các thím ai cũng mua leetcode premium hết hở

Có @freedom.9 thôi, tranh thủ thím ấy chưa vào FAANG lo nâng bi đi nhé, mốt thím ấy phát card cho, ko là không kịp đâu

noobdev · 10/9/24

bkhoang đã nói:
C#:

public class Solution { public int LastStoneWeightII(int[] stones) { var possibility = new List<int>{ 0 }; foreach (var t in stones) { var length = possibility.Count; var casePlus = possibility.Select(x => x + t).ToList(); possibility = possibility.Select(x => Math.Abs(x - t)).Union(casePlus).ToList(); } return possibility.Min(); } }

chưa tối ưu lắm, nhờ các thím xem qua chứ mới beat 70% TC

Cái này là BF rồi, mà ko bị dính TLE nhỉ, mình python dùng backtrack ko tối ưu gì TLE lòi mắt, nhưng về cơ bản bài này tối ưu thì là m*sum(stones), cách thì cũng phải dùng trick ảo vãi, ko làm trước gặp bài này lúc interview khéo hẹo chắc.

noobdev · 10/9/24

vicejuniordev đã nói:
Nó là brute force đó thím vì mình sẽ phải duyệt qua tất cả các cặp có khả năng xảy ra (exploring all possibilities) . Bài này mình cũng làm khá lâu rồi nhưng vừa xem lại thì mình làm theo cách Top-down vì thấy nó intuitive hơn (đối với mình). Còn bài Knapsack là bài nhập môn Dynamic Programming đó (chọn hoặc không chọn).

Còn bài này pattern thì viết ra giấy là sẽ ra. Ví dụ : [2,7,4,1,8,1] mình có thì nó sẽ là
(2-7) (4-1) (8-1) or (2-4) (7-1) (8-1) ...=> 5 3 7 => (5 - 3) 7 or (5-7) 3 => Res = 1

Nhìn vào đấy thì sẽ thấy pattern là thêm dấu ( + hoặc -) vào trước số hiện tại trong mảng rồi cộng với current sum rồi check xem giá trị nào nhỏ hơn.

Python:

# Approach 1 : Recursive - top down + memorize n = len(stones) @lru_cache(None) def helper(i, curr): if i >= n: return abs(curr) return min(helper(i + 1, curr - stones[i]),helper(i + 1, curr + stones[i])) return helper(0,0)

Dựa vào đâu come up được cái intuition này thế bác? có cái pattern nào cụ thể ko? bài này thấy nhiều người ghi nào 01 Knapsack nhưng bản chất từ đâu để đưa về 01 Knapsack nó lại khác hoàn toàn.

vicejuniordev · 10/9/24

noobdev đã nói:
Dựa vào đâu come up được cái intuition này thế bác? có cái pattern nào cụ thể ko? bài này thấy nhiều người ghi nào 01 Knapsack nhưng bản chất từ đâu để đưa về 01 Knapsack nó lại khác hoàn toàn.

Nháp ra giấy là sẽ ra (+num1 - num2) (+num3 - num4)…., bản chất là thêm dấu +/- vào trước thôi…

via theNEXTvoz for iPhone

Phó GOAT · 10/9/24

Cố Trường Ca đã nói:
Có @freedom.9 thôi, tranh thủ thím ấy chưa vào FAANG lo nâng bi đi nhé, mốt thím ấy phát card cho, ko là không kịp đâu

Thấy vozer đồn là @freedom.9 vào FAANG lương mấy trăm k $/năm rồi mà nhỉ

noobdev · 10/9/24

Cố Trường Ca đã nói:
Cơm thêm

https://leetcode.com/problems/profitable-schemes/description/

đù má TLE 41/46, đọc thấy cái trick min(minProfit, curPro+profit) đúng đỉnh, ai nghĩ ra đc cái này cũng thông minh đấy, bác nhận em 1 respect

Uruna117 · 10/9/24

noobdev đã nói:
Dựa vào đâu come up được cái intuition này thế bác? có cái pattern nào cụ thể ko? bài này thấy nhiều người ghi nào 01 Knapsack nhưng bản chất từ đâu để đưa về 01 Knapsack nó lại khác hoàn toàn.

Cái này trong solution có bác hướng dẫn ấy ông, ý tưởng phân ra 2 bịch đá S1 và S2 mà S1 + S2 = total, đồng thời kết quả cần tìm là S1 - S2 = res, do đó thế trên vào thì res = total - 2 * S2, với mấy cái kia là hằng số thì mình maximize thằng S2 với giá trị cap của S2 là total / 2 cũng là max weight của knapsack luôn.

freedom.9 · 10/9/24

Cố Trường Ca đã nói:
Kiếm đâu ra code của vozlit vậy fèn

tìm max trong dfs được mà sao phải sort với binary search chi

Python:

class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) target = total // 2 memo = {} self.largestSum = 0 def dfs(index, sumSoFar): if sumSoFar > target: return if index == len(stones): self.largestSum = max(self.largestSum, sumSoFar) return if (index, sumSoFar) in memo: return memo[(index, sumSoFar)] dfs(index + 1, sumSoFar + stones[index]) dfs(index + 1, sumSoFar) memo[(index, sumSoFar)] = self.largestSum dfs(0, 0) return total - 2 * self.largestSum

Chưa đủ trình độ ko hiểu được tinh hoa trong này đâu

Cách này dùng trong trường hợp n <= 40 và sum lớn, với max num 10^7.
Thay vì backtrack sẽ cho ra kết quả 2^40 thì chuyển về 2^20log(2^20)

via theNEXTvoz for iPhone

Mỹ Chu Lang · 10/9/24

C#:

public class Solution {
    public int GreatestCommonDivisior(int a, int b)
    {
        int remainder = 0;
        while(b != 0)
        {
            remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }
    
    public ListNode InsertGreatestCommonDivisors(ListNode head) {
        var temp = head;
        while(temp.next != null)
        {
            var newNode = new ListNode()
            {
                val = GreatestCommonDivisior(temp.val, temp.next.val),
                next = temp.next
            };
            temp.next = newNode;
            temp = temp.next.next;
        }
        return head;
    }
}

chiyeuemthoi · 10/9/24

Mã:

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head
        while current and current.next:
            firstVal = current.val
            secondVal = current.next.val
            gcdNode = ListNode(gcd(firstVal, secondVal))  
            gcdNode.next = current.next  
            current.next = gcdNode  
            current = gcdNode.next  
        return head

Cố Trường Ca · 10/9/24

freedom.9 đã nói:
Chưa đủ trình độ ko hiểu được tinh hoa trong này đâu

Cách này dùng trong trường hợp n <= 40 và sum lớn, với max num 10^7.
Thay vì backtrack sẽ cho ra kết quả 2^40 thì chuyển về 2^20log(2^20)

via theNEXTvoz for iPhone

backtrack khi có mem thì khác, với dfs(index, curSum), với mỗi tuple (index, curSum) chỉ gọi dfs một lần duy nhất với mem. với index in range(0, n) curSum in range (0, total/2) thì cùng lắm worse case chỉ có O(n * total)

Còn của anh là O(2^(n/2) * n) do đoạn binary search

nahnahinin · 10/9/24

rồng tranh luận tôm tép đứng hóng

Cố Trường Ca · 10/9/24

nahnahinin đã nói:
rồng tranh luận tôm tép đứng hóng

làm gì có rồng nào rating 1300

freedom.9 · 10/9/24

Cố Trường Ca đã nói:
backtrack khi có mem thì khác, với dfs(index, curSum), với mỗi tuple (index, curSum) chỉ gọi dfs một lần duy nhất với mem. với index in range(0, n) curSum in range (0, total/2) thì cùng lắm worse case chỉ có O(n * total)

Còn của anh là O(2^(n/2) * n) do đoạn binary search

Thế giờ cho nums <= 10^7 thì fence làm thế nào :doubt:

vấn đề ở chỗ là với nums lớn thì fence sẽ ko xài được DP hiểu ko.
Chứ bài kia thì xài DP là ok rồi, vì nums chỉ có khoảng <=100 thì DP sẽ cho ra time complexity là O(n*k)
Vấn đề là fence sẽ ko thể nào giải O(n*k) cho nums <= 10^7 được. Thế nên mới phải cần meet in the middle, như bài này này.

https://leetcode.com/problems/closest-subsequence-sum/description/

small-lambda · 10/9/24

nahnahinin đã nói:
rồng tranh luận tôm tép đứng hóng

rồng nhầm và phồng tôm

MasonMaoSuVuong · 10/9/24

Cố Trường Ca đã nói:
làm gì có rồng nào rating 1300

hay cho 1 rồng giả heo ăn thịt hổ.

Cố Trường Ca · 10/9/24

freedom.9 đã nói:
Thế giờ cho nums <= 10^7 thì fence làm thế nào vấn đề ở chỗ là với nums lớn thì fence sẽ ko xài được DP hiểu ko.
Chứ bài kia thì xài DP là ok rồi, vì nums chỉ có khoảng <=100 thì DP sẽ cho ra time complexity là O(n*k)
Vấn đề là fence sẽ ko thể nào giải O(n*k) cho nums <= 10^7 được. Thế nên mới phải cần meet in the middle, như bài này này.

https://leetcode.com/problems/closest-subsequence-sum/description/

Đã hiểu

Cảm ơn thím đã khai sáng
+1 điểm tình bạn (Mốt nhớ phát card nhiều

)

Cố Trường Ca · 10/9/24

small-lambda đã nói:
rồng nhầm và phồng tôm

thèm gạch hả fen, đợi 2 tháng nhé

Cố Trường Ca · 10/9/24

MasonMaoSuVuong đã nói:
hay cho 1 rồng giả heo ăn thịt hổ.

Heo thật

chubemuidai · 10/9/24

ngồi nghe thôi chứ hard thì skip :too_sad:

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

Senior Member

Member

Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này