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

bribnt · Jul 11, 2022

dagedage said:
xin đóng góp 1 lời giải cho bài hnay các bác ạ
https://leetcode.com/submissions/detail/743881279/
em dùng queue duyệt hết toàn bộ các node trên cây, có bác nfo có cách ko cần duyệt hết không ạ

Không có cách nào cả.
Bởi vì node right-most ở level n+1 có thể là con của một node level n bất kỳ nào đó.

Sunday_Sunday · Jul 11, 2022

tdat00 said:
Hôm thứ 6 lười làm bài Hard nên mất streak 70 ngày nên lười hẳn các thím ạ, cuối tuần toàn đi chơi chả muốn làm task giờ mới vào guồng trở lại

Bài sáng nay thì tôi dùng queue cho đơn giản

https://leetcode.com/submissions/detail/743808725/

C#:

public class Solution { public IList<int> RightSideView(TreeNode root) { List<int> ret = new (); if (root == null) return ret; Queue<TreeNode> q = new(); TreeNode current = null; q.Enqueue(root); while (q.Count > 0) { int count = q.Count; for (var i = 0; i < count; i++) { current = q.Dequeue(); if (current.left != null) q.Enqueue(current.left); if (current.right != null) q.Enqueue(current.right); } ret.Add(current.val); } return ret; } }

bỏ redeem mua lại lượt là đc mà bác
em mới phá max streak 41, giờ đang 43

Arik97 · Jul 11, 2022

tdat00 said:
Hôm thứ 6 lười làm bài Hard nên mất streak 70 ngày nên lười hẳn các thím ạ, cuối tuần toàn đi chơi chả muốn làm task giờ mới vào guồng trở lại

Bài sáng nay thì tôi dùng queue cho đơn giản

https://leetcode.com/submissions/detail/743808725/

C#:

public class Solution { public IList<int> RightSideView(TreeNode root) { List<int> ret = new (); if (root == null) return ret; Queue<TreeNode> q = new(); TreeNode current = null; q.Enqueue(root); while (q.Count > 0) { int count = q.Count; for (var i = 0; i < count; i++) { current = q.Dequeue(); if (current.left != null) q.Enqueue(current.left); if (current.right != null) q.Enqueue(current.right); } ret.Add(current.val); } return ret; } }

voz có ai redeem đc cái áo leetcode chưa nhỉ. ham cái áo vl nhưng mà theo tính toán thì phải streak 10 tháng nữa mới đủ 6k điểm

đấy là mua premium rồi đấy :go:

Sent from Samsung SM-G986U1 using vozFApp

Sunday_Sunday · Jul 11, 2022

Arik97 said:
voz có ai redeem đc cái áo leetcode chưa nhỉ. ham cái áo vl nhưng mà theo tính toán thì phải streak 10 tháng nữa mới đủ 6k điểm đấy là mua premium rồi đấy

Sent from Samsung SM-G986U1 using vozFApp

bác cho hỏi mua premium thì được thêm redeem à
em thì cũng chỉ làm hằng ngày thì +11
1 tháng được +25 vì streak 25 của tháng

Blue Amethyst · Jul 11, 2022

Arik97 said:
voz có ai redeem đc cái áo leetcode chưa nhỉ. ham cái áo vl nhưng mà theo tính toán thì phải streak 10 tháng nữa mới đủ 6k điểm đấy là mua premium rồi đấy

Sent from Samsung SM-G986U1 using vozFApp

hình như có bác @kunguyenqt ấy bác, mà thấy bác ấy cũng cày hard lắm :extreme_sexy_girl:

Sunday_Sunday · Jul 11, 2022

Blue Amethyst said:
hình như có bác @kunguyenqt ấy bác, mà thấy bác ấy cũng cày hard lắm

hình như bác chủ topic này cũng có mà. ngay page 2 thì phải :beauty:

_Gia_Cat_Luong_ · Jul 11, 2022

Sunday_Sunday said:
hình như bác chủ topic này cũng có mà. ngay page 2 thì phải

Hong có nha, thoy lên sộp pi đặt in 150k 1 cái cho đỡ thèm. 6k coin biết đến khi nào T_T.
:cry:

tdat00 · Jul 11, 2022

Sunday_Sunday said:
bỏ redeem mua lại lượt là đc mà bác
em mới phá max streak 41, giờ đang 43

Arik97 said:
voz có ai redeem đc cái áo leetcode chưa nhỉ. ham cái áo vl nhưng mà theo tính toán thì phải streak 10 tháng nữa mới đủ 6k điểm đấy là mua premium rồi đấy

Sent from Samsung SM-G986U1 using vozFApp

Redeem mua lượt submit cho bài cũ được nhé, tôi redeem 2 lần rồi. Nhưng mà vẫn còn lười chưa muốn làm lại mấy bài cuối tuần trước, để hôm nào khác vậy :angry:

Còn cái áo thì ra tiệm áo thun đặt họ in cho chục cái :extreme_sexy_girl:

Sunday_Sunday · Jul 11, 2022

tdat00 said:
Redeem mua lượt submit cho bài cũ được nhé, tôi redeem 2 lần rồi. Nhưng mà vẫn còn lười chưa muốn làm lại mấy bài cuối tuần trước, để hôm nào khác vậy

Còn cái áo thì ra tiệm áo thun đặt họ in cho chục cái

in thì nó cảm xúc gì đâu bác :ah:

Arik97 · Jul 11, 2022

Sunday_Sunday said:
bác cho hỏi mua premium thì được thêm redeem à
em thì cũng chỉ làm hằng ngày thì +11
1 tháng được +25 vì streak 25 của tháng

có thêm weekly premium nữa nhé. mỗi bài +35. 1 tháng thêm đc 35x5 :cautious:

Sent from Samsung SM-G986U1 using vozFApp

Sunday_Sunday · Jul 11, 2022

Arik97 said:
có thêm weekly premium nữa nhé. mỗi bài +35. 1 tháng thêm đc 35x5

Sent from Samsung SM-G986U1 using vozFApp

thế bác chỉ có tham gia contest là nhanh nhất thôi :big_smile:

tdat00 · Jul 11, 2022

Sunday_Sunday said:
in thì nó cảm xúc gì đâu bác

Mặc vào ra đường chắc cả năm mới có được 1 thằng biết được ý nghĩa của cái áo, mà dễ gì nó biết được áo authen hay áo pha ke :angry:

kunguyenqt · Jul 11, 2022

Arik97 said:
voz có ai redeem đc cái áo leetcode chưa nhỉ. ham cái áo vl nhưng mà theo tính toán thì phải streak 10 tháng nữa mới đủ 6k điểm đấy là mua premium rồi đấy

Sent from Samsung SM-G986U1 using vozFApp

Review:

Áo Leetcode chất liệu vải cùi, giặt nhanh sờn, chỉ khâu cắt không khéo, tem mác cũng nhìn rất khựa, nói chung là khá rẻ tiền.
Được cái form ôm khá đẹp, mang cũng thoải mái, tự tin khoe cá tính, với logo in tốt, hiện chưa bị bay chữ.

Kết: Thua xa áo AWS. Thôi thà mua áo tự in còn đẹp hơn. :confident:

ngx3009 · Jul 11, 2022

Xin chào các bác, em cứ tưởng 2 đoạn code sau đây là cùng độ phức tạp chứ nhỉ nhưng cái duyệt for theo index lại chậm hơn cái còn lại, ai giải đáp giúp em với :pudency:

(accounts là mảng 2 chiều)

Java:

   for(int i = 0; i < accounts.length; i++){
             int sum = 0;
             for(int j = 0; j < accounts[i].length; j++){
                sum += accounts[i][j];
            }
             if(sum > max){
                max = sum;
             }
    }

Java:

      for(int[] c : accounts){
            int sum = 0;
            for(int money : c){
                sum += money;
            }
             if(sum > max){
                max = sum;
            }
        }

tdat00 · Jul 11, 2022

ngx3009 said:
Xin chào các bác, em cứ tưởng 2 đoạn code sau đây là cùng độ phức tạp chứ nhỉ nhưng cái duyệt for theo index lại chậm hơn cái còn lại, ai giải đáp giúp em với (accounts là mảng 2 chiều)

Java:

for(int i = 0; i < accounts.length; i++){ int sum = 0; for(int j = 0; j < accounts[i].length; j++){ sum += accounts[i][j]; } if(sum > max){ max = sum; } }

Java:

for(int[] c : accounts){ int sum = 0; for(int money : c){ sum += money; } if(sum > max){ max = sum; } }

Thím dùng cái gì để benchmark? Muốn chính xác thì phải dùng các hàm diagnostic của thư viện để đo từng Tick count ấy. Như trong .Net thì có attribute [Benchmark] để gắn vào đầu mỗi hàm.

Sent from Samsung SM-A528B using vozFApp

ngx3009 · Jul 11, 2022

tdat00 said:
Thím dùng cái gì để benchmark? Muốn chính xác thì phải dùng các hàm diagnostic của thư viện để đo từng Tick count ấy. Như trong .Net thì có attribute [Benchmark] để gắn vào đầu mỗi hàm.

Sent from Samsung SM-A528B using vozFApp

kiểu em làm bài trên leetcode ý thì dùng cái bên dưới chạy lại nhanh hơn cái duyệt for theo index

kyo_pyro · Jul 11, 2022

ngx3009 said:
kiểu em làm bài trên leetcode ý thì dùng cái bên dưới chạy lại nhanh hơn cái duyệt for theo index

Leetcode cùng 1 source submit 2 lần time nó còn khác nhau mà thím

tdat00 · Jul 12, 2022

Bài sáng nay thấy số nhỏ mà cũng chua phết. Hết TLE rồi lại đến Out Memory, 7 lần submit mới qua được

Đệ quy thôi, với mỗi stick thì cộng vào 1 trong 4 cạnh a, b, c, d rồi duyệt qua stick kế tiếp. Đến khi hết stick mà thấy a == b == c == d thì trả về true.
Dĩ nhiên là cần phải có memo table để giảm bớt số hàm đệ quy thừa nhằm tránh TLE. Dễ thấy chúng ta không cần quan tâm thứ tự các cạnh a, b, c, d => sort 4 cạnh này trước khi đưa vào memo table.
Đến lúc này solution đã tương đối ổn áp. Nhưng leetcode có giới hạn memory nên chúng ta vẫn cần phải giảm bớt số item trong memo table => cần tính tổng các sticks trước rồi chia 4 để lấy ra độ dài mỗi cạnh => trong hàm đệ quy nếu vượt quá độ dài này thì bỏ qua luôn không cần quan tâm nữa.

https://leetcode.com/submissions/detail/744745732/

C#:

public class Solution {
    Dictionary<(int a, int b, int c, int d), bool> memo = new ();
    int maxLen = 0;

    public bool Makesquare(int[] matchsticks) {
        int sum = matchsticks.Sum();
        if (sum % 4 != 0)
            return false;
        
        maxLen = sum / 4;
        return isValid(matchsticks, 0, 0, 0, 0, 0);
    }
    
    bool isValid(int[] sticks, int index, int a, int b, int c, int d)
    {
        if (index >= sticks.Length)
        {
            return a == b && b == c && c == d;
        }
        
        // sort numbers so that a <= b <= c <= d
        (a, b, c, d) = sort(a, b, c, d);
        
        if (memo.ContainsKey((a, b, c, d)))
            return memo[(a, b, c, d)];
        
        bool ret = false;
        
        if (a + sticks[index] <= maxLen)
            ret = ret || isValid(sticks, index+1, a + sticks[index], b, c, d);
        
        if (b + sticks[index] <= maxLen)
            ret = ret || isValid(sticks, index+1, a, b + sticks[index], c, d);
        
        if (c + sticks[index] <= maxLen)
            ret = ret || isValid(sticks, index+1, a, b, c + sticks[index], d);
        
        if (d + sticks[index] <= maxLen)
            ret = ret || isValid(sticks, index+1, a, b, c, d + sticks[index]);
        
        memo[(a, b, c, d)] = ret;
        return ret;
    }
    
    (int a, int b, int c, int d) sort(int a, int b, int c, int d)
    {
        (a, b) = a > b ? (b, a) : (a, b);
        (c, d) = c > d ? (d, c) : (c, d);
        (a, c) = a > c ? (c, a) : (a, c);
        (b, d) = b > d ? (d, b) : (b, d);
        (b, c) = b > c ? (c, b) : (b, c);
        
        return (a, b, c, d);
    }
}

vtproduction2 · Jul 12, 2022

cũng phải luyện dần mấy cái này thôi, làm mobile dev mà đi pv toàn round đầu cho mấy bài giải thuật, haiz

_Gia_Cat_Luong_ · Jul 12, 2022

12/07/2022

#473. (Medium) Matchsticks to Square

Phân tích bài toán:

Vì mỗi que diêm có chiều dài là số nguyên, nên dễ thấy cạnh hình vuông cần tạo thành cũng sẽ là số nguyên
Đồng thời, cạnh này sẽ có chiều dài là tổng của tất cả que diêm chia 4. Dĩ nhiên nếu tổng này không chia hết cho 4 thì đáp án mặc định là False
Vậy, để tạo ra một cạnh hình vuông ta cần lựa ra một tập các que diêm sao cho tổng của chúng bằng chiều dài cạnh đã tìm
Sau đó, chúng ta sẽ tìm 3 cạnh còn lại từ các que diêm bằng phương pháp tương tự
Nói cách khác, bài toán trở thành phân các que diêm thành 4 tập con sao cho tổng của mỗi tập đúng bằng cạnh cần tìm

Giả sử như ta chỉ cần tìm một cạnh, dễ thấy đây là bài toán kinh điển, tìm tập con có tổng bằng k mà ta đã biết cách giải bằng QHĐ.
Mỗi khi chọn xong một cạnh, ta lại thực hiện thuật toán tương tự để tìm cho các cạnh còn lại, tuy nhiên ta phải loại trừ các que đã chọn trước đó ra
Để lưu trữ và kiểm tra xem một que đã được chọn hay chưa, ta có thể dùng bitmask vì trong bài này số lượng tối đa của các que diêm chỉ có 16.
Tối ưu thêm một chút, dễ thấy ta chỉ cần tìm 3 cạnh thay vì cả 4 cạnh, vì cạnh còn lại mặc nhiên sẽ đúng.

Code:
https://leetcode.com/submissions/detail/744754269/

Nhận xét:

Solution này có độ phức tạp O(3^n) vì mỗi que diêm có 3 lựa chọn thuộc về 3 cạnh
Tuy nhiên, kết hợp với bitmask độ phức tạp suy biến về O(3*2^n) ~ O(2^n) vì mỗi cạnh chỉ còn 2 lựa chọn, không quan tâm nó thuộc về cạnh nào.

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

Đã tốn tiền

Junior Member

Senior Member

Junior Member

Junior Member

Junior Member

Senior Member

Đã tốn tiền

Junior Member

Senior Member

Junior Member

Đã tốn tiền

Junior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Đã tốn tiền

Junior Member

Senior Member

12/07/2022​

Similar threads

Share this page

12/07/2022