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

[_Gia_Cat_Luong_]

Vấn đề khó hiểu là em debug local nó chạy nhưng lên leetcode kết quả lại khác

Thím phải đọc cái custom judge của nó trong đề bài. Đại ý là thím phải modify trên chính cái arr đó luôn chứ không được tạo ra arr mới. Mà đoạn Where của thím là tạo ra arr mới rồi

 

[dangson]

Nay mới biết thớt này.
Có ai Python ko?

return reduce(lambda p, _: [p[1], sum(p)], range(n), [0, 1])[0]

 

[ngoctan_95]

Hello các fen mình đang làm bài xóa những phần tử bị lặp trong 1 mảng đã được sorted. Mà không hiểu sao code C# của mình trên Visual studio thì chạy đúng, mà chạy trên leetcode lại ra sai.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

View attachment 1249206

Code của mình

public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 1)
                return 1;

            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                    {
                        nums = nums.Where((val, index) => index != j).ToArray();
                        count++;
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
            }

           
            return count;
    }

Sao phải 2 for vậy @@ Bài này 1 for là đủ rồi

• Kiểm tra empty thì return 0, đặt b = res = 0
• Loop từ đầu tới cuối, kiểm tra nums[a] và nums khác nhau k, có thì b tăng 1 đơn vị, còn nums gán bằng nums[a]
  [*]Kết quả trả về sẽ bằng b = head giao với tail + 1 mà head giao tail = b => return b + 1 là được
  

 

[Sơn Tiêu Nguy]

share với các thím 2 solution 0ms của em cho bài fibonacci

Spoiler: Java Fast Doubling

class Solution {
    public int fib(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 1;
            default:
                if (n % 2 == 0) {
                    n = n / 2;

                    return fib(n) * (2 * fib(n + 1) - fib(n));
                }

                n = n / 2;

                return fib(n + 1) * fib(n + 1) + fib(n) * fib(n);
        }
    }
}

Spoiler: Java Bựa

class Solution {
    public int fib(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 1;
            case 3:
                return 2;
            case 4:
                return 3;
            case 5:
                return 5;
            case 6:
                return 8;
            case 7:
                return 13;
            case 8:
                return 21;
            case 9:
                return 34;
            case 10:
                return 55;
            case 11:
                return 89;
            case 12:
                return 144;
            case 13:
                return 233;
            case 14:
                return 377;
            case 15:
                return 610;
            case 16:
                return 987;
            case 17:
                return 1597;
            case 18:
                return 2584;
            case 19:
                return 4181;
            case 20:
                return 6765;
            case 21:
                return 10946;
            case 22:
                return 17711;
            case 23:
                return 28657;
            case 24:
                return 46368;
            case 25:
                return 75025;
            case 26:
                return 121393;
            case 27:
                return 196418;
            case 28:
                return 317811;
            case 29:
                return 514229;
            case 30:
                return 832040;
            default:
                return -1;
        }
    }
}

 

[Sunday_Sunday]

share với các thím 2 solution 0ms của em cho bài fibonacci

Spoiler: Java Fast Doubling

class Solution {
    public int fib(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 1;
            default:
                if (n % 2 == 0) {
                    n = n / 2;

                    return fib(n) * (2 * fib(n + 1) - fib(n));
                }

                n = n / 2;

                return fib(n + 1) * fib(n + 1) + fib(n) * fib(n);
        }
    }
}

Spoiler: Java Bựa

class Solution {
    public int fib(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return 1;
            case 3:
                return 2;
            case 4:
                return 3;
            case 5:
                return 5;
            case 6:
                return 8;
            case 7:
                return 13;
            case 8:
                return 21;
            case 9:
                return 34;
            case 10:
                return 55;
            case 11:
                return 89;
            case 12:
                return 144;
            case 13:
                return 233;
            case 14:
                return 377;
            case 15:
                return 610;
            case 16:
                return 987;
            case 17:
                return 1597;
            case 18:
                return 2584;
            case 19:
                return 4181;
            case 20:
                return 6765;
            case 21:
                return 10946;
            case 22:
                return 17711;
            case 23:
                return 28657;
            case 24:
                return 46368;
            case 25:
                return 75025;
            case 26:
                return 121393;
            case 27:
                return 196418;
            case 28:
                return 317811;
            case 29:
                return 514229;
            case 30:
                return 832040;
            default:
                return -1;
        }
    }
}

phương án 2 đẳng cấp thật sự

 

[Violet_7]

7/7/2022:

• 1 câu medium quen thuộc
• nhìn vào đề bài khá quen thuộc, 2 string so le nhau để tạo ra string thứ 3 -> nghĩ ngay tới quy hoạch động 2 chiều
• tạo mảng qhđ 2 chiều dp sao cho dp[i.][j.] là check xem s1.substr(1->i) và s2.substr(1->j) có tạo đc s3.substr(1->(i+j)), nếu dp[i.][j.] = true thì tạo đc
• duyệt i từ 1->s3.length
• check xem tất cả các th từ s1, s2 tạo đc s3
• vd: i == 4 -> check dp[0][4], dp[1][3], dp[2][2], dp[3][1], dp[4][0]
• Tại i == 1 sẽ biết đc dp[0][1], dp[1][0] bằng true hay false
• giả sử dp[0][1] = true và dp[1][0] = true
• đến i = 2, nếu s1[0] == s3[1] -> dp[1][1] = true vì dp[0][1] == true
• nếu s2[0] == s3[1] -> dp[1][1] = true vì dp[1][0] = true
• cứ tiếp tục đến s3.length
• ra đáp án
• Time: O(s3.length * min(s1.length, s2.length))
• Code: https://leetcode.com/submissions/detail/740511320/
• Bài khá quen, nghĩ mất 5p mà hôm qua thức khuya nên code và fix bug 15p
• Khi tạo đc solution space O(n*m) thì để space O(m) cx khá dễ, mấy bài như này cứ dùng mảng 2 chiều cho dễ rồi chuyển về mảng 1 chiều thì đơn giản hơn

- Solution: O(n) space https://leetcode.com/submissions/detail/740534711/

 

[tdat00]

Bài sáng nay thì biết chắc là quy hoạch động rồi, nhưng cái đó thì tôi gà vkl nên hay dùng đệ quy + memo cho nhẹ đầu.

Spoiler: solution

• Đơn giản là so sánh từng ký tự của s3 với s1 và s2. Ví dụ với s3[0]:
  1. Nếu khác s1[0] lẫn s2[0] => nhanh chóng trả false
  2. Nếu khác s1[0] và giống s2[0] => chuyển qua so sánh s3[1] với (s1[0] hoặc s2[1]).
  3. Nếu giống s1[0] và khác s2[0] => chuyển qua so sánh s3[1] với (s1[1] hoặc s2[0]).
  4. Nếu giống s1[0] lẫn s2[0] => lúc này có 2 khả năng xảy ra: chọn s1[0] hoặc chọn s2[0] => đệ quy cả 2 trường hợp rồi AND lại thành kết quả.

Spoiler: code

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

Code chuối nên chưa tính được độ phức tạp như thế nào

Do có memo nên hình như TC là O(m*n) không biết có đúng ko nưa.

public class Solution {
    Dictionary<int, bool> memo = new ();
    int StopKey = 0;
 
    public bool IsInterleave(string s1, string s2, string s3) {
        if (s3.Length != s1.Length + s2.Length)
            return false;
     
        StopKey = (s1.Length << 24) | (s2.Length << 16) | (s3.Length);

        return valid(s1, 0, s2, 0, s3, 0);
    }
 
    private bool valid(string s1, int i1, string s2, int i2, string s3, int i3)
    {
        if (memo.ContainsKey(StopKey))
            return memo[StopKey];

        int key = (i1 << 24) | (i2 << 16) | i3;
        if (!memo.ContainsKey(key))
        {
            bool val = true;

            if (i1 < s1.Length && i2 < s2.Length)
            {
                if (s3[i3] != s1[i1] && s3[i3] != s2[i2])
                    val = false;
                else if (s3[i3] != s1[i1])
                    val = valid(s1, i1, s2, i2+1, s3, i3+1);
                else if (s3[i3] != s2[i2])
                    val = valid(s1, i1+1, s2, i2, s3, i3+1);
                else
                    val = valid(s1, i1+1, s2, i2, s3, i3+1) || valid(s1, i1, s2, i2+1, s3, i3+1);
            }
            else if (i1 < s1.Length) // && i2 >= s2.Length
            {
                val = s3[i3] == s1[i1] && valid(s1, i1+1, s2, i2, s3, i3+1);
            }
            else if (i2 < s2.Length) // i1 >= s1.Length
            {
                val = s3[i3] == s2[i2] && valid(s1, i1, s2, i2+1, s3, i3+1);
            }
         
            memo[key] = val;
        }
     
        return memo[key];
    }
}

 

[thuyduong2007]

Gặp bài này thì cứ auto táng dp + memo cho nó nhẹ đầu, dùng python nữa thì càng khỏe. Còn follow up question tính sau.

Spoiler

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        @cache
        def isInterleaveRecursive(i1 = 0, i2 = 0) ->bool:
            if i1 + i2 == len(s3) \
            or (i1 < len(s1) and s1[i1] == s3[i1+i2] and isInterleaveRecursive(i1+1, i2)) \
            or (i2 < len(s2) and s2[i2] == s3[i1+i2] and isInterleaveRecursive(i1, i2+1)) :
                return True
            return False
        return isInterleaveRecursive()

Cách này TC và SC đều là O(s1.length*s2.length).

 

[...Batman...]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != (s2.size() + s1.size())){
            return false;
        }
        if (s3 == (s1 + s2))
            return true;
        
        if ((s3[0] != s1[0]) && (s3[0] != s2[0]))
            return false;
        
        bool a1=false, a2=false;
        
        if (s3[0] == s1[0])
            a1 = isInterleave(s1.substr(1), s2, s3.substr(1));
        
        if (s3[0] == s2[0])
            a2 = isInterleave(s1, s2.substr(1), s3.substr(1));
        
        return (a1 || a2);
    }
};

Em code theo các solution bên trên mà sao toàn bị quá thời gian vậy

 

[thuyduong2007]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != (s2.size() + s1.size())){
            return false;
        }
        if (s3 == (s1 + s2))
            return true;
       
        if ((s3[0] != s1[0]) && (s3[0] != s2[0]))
            return false;
       
        bool a1=false, a2=false;
       
        if (s3[0] == s1[0])
            a1 = isInterleave(s1.substr(1), s2, s3.substr(1));
       
        if (s3[0] == s2[0])
            a2 = isInterleave(s1, s2.substr(1), s3.substr(1));
       
        return (a1 || a2);
    }
};

Em code theo các solution bên trên mà sao toàn bị quá thời gian vậy

Có 2 nguyên nhân:
1. Không lưu kết quả trung gian để tái sử dụng. Xem chi tiết ở đây, nhất là phần memoi:

2. Dùng substr độ phức tạp O(n). Giải pháp là dùng biến index để count.

 

[Lập Trình Viên Số Khổ]

Có 2 nguyên nhân:
1. Không lưu kết quả trung gian để tái sử dụng. Xem chi tiết ở đây, nhất là phần memoi:

2. Dùng substr độ phức tạp O(n). Giải pháp là dùng biến index để count.

sao của e có 5.15 bác ơi

 

[Lập Trình Viên Số Khổ]

Gặp bài này thì cứ auto táng dp + memo cho nó nhẹ đầu, dùng python nữa thì càng khỏe. Còn follow up question tính sau.

Spoiler

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        @cache
        def isInterleaveRecursive(i1 = 0, i2 = 0) ->bool:
            if i1 + i2 == len(s3) \
            or (i1 < len(s1) and s1[i1] == s3[i1+i2] and isInterleaveRecursive(i1+1, i2)) \
            or (i2 < len(s2) and s2[i2] == s3[i1+i2] and isInterleaveRecursive(i1, i2+1)) :
                return True
            return False
        return isInterleaveRecursive()

Cách này TC và SC đều là O(s1.length*s2.length).

Nếu ko dùng @cache thì tạo bảng memo (implement bằng tay) như nào bác, em thấy hơi ảo:

hàm isInterleaveRecursive nhận 2 số nguyên ví dụ isInterleaveRecursive(2,3)
thì có 2 case là s1 điền trước, s2 điền trước, mà chỉ có 1 cái đúng, cái kia sai, thì isInterleaveRecursive(2,3) = False sẽ skip hết các đệ quy phía sau,

 

[thuyduong2007]

Nếu ko dùng @cache thì tạo bảng memo (implement bằng tay) như nào bác, em thấy hơi ảo:

hàm isInterleaveRecursive nhận 2 số nguyên ví dụ isInterleaveRecursive(2,3)
thì có 2 case là s1 điền trước, s2 điền trước, mà chỉ có 1 cái đúng, cái kia sai, thì isInterleaveRecursive(2,3) = False sẽ skip hết các đệ quy phía sau,

1. cái @cache bản chất nó lưu kết quả của function vào dict với key là các param của function. Solution bên trên chạy chậm là do dùng 3 cái string làm param cho cái check function dẫn đến tính hash value cho cache chậm. Đổi lại dùng index là số int như solution của t sẽ nhanh hơn nhiều. Sau đó muốn tự implement cái memoi thì làm bảng s1.length*s2.length rồi tự xử lý việc lưu với lấy kết quả tạm trong đó.
2. Code của ông đọc đau não quá.
t đoán là do cái vòng for đó, nó fail cái đó thì nó back lại cái trước rồi chạy for tiếp thôi

 

[Lập Trình Viên Số Khổ]

1. cái @cache bản chất nó lưu kết quả của function vào dict với key là các param của function. Solution bên trên chạy chậm là do dùng 3 cái string làm param cho cái check function dẫn đến tính hash value cho cache chậm. Đổi lại dùng index là số int như solution của t sẽ nhanh hơn nhiều. Sau đó muốn tự implement cái memoi thì làm bảng s1.length*s2.length rồi tự xử lý việc lưu với lấy kết quả tạm trong đó.
2. Code của ông đọc đau não quá.
t đoán là do cái vòng for đó, nó fail cái đó thì nó back lại cái trước rồi chạy for tiếp thôi

vâng, chắc do vòng for nên nó chạy chậm, nhưng e ko hiểu cách giải của bác sao lại chạy đúng, giải thích như nào để có thể code ra như vậy bác

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        @cache
        def isInterleaveRecursive(i1 = 0, i2 = 0) ->bool:
            return i1 + i2 == len(s3) \
            or (i1 < len(s1) and s1[i1] == s3[i1+i2] and isInterleaveRecursive(i1+1, i2)) \
            or (i2 < len(s2) and s2[i2] == s3[i1+i2] and isInterleaveRecursive(i1, i2+1)) 
        return isInterleaveRecursive()

Em ngồi ngẫm nghĩ mãi không hiểu tại sao bác nghĩ ra cách đệ quy này,
Vì cách em nghĩ là y hệt như đề bài ra, chỉ là làm ngắn string lại

Còn cách của bác nó mới tricky, nên em không biết các suy luận như nào

 

[_Gia_Cat_Luong_]

vâng, chắc do vòng for nên nó chạy chậm, nhưng e ko hiểu cách giải của bác sao lại chạy đúng, giải thích như nào để có thể code ra như vậy bác

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        @cache
        def isInterleaveRecursive(i1 = 0, i2 = 0) ->bool:
            return i1 + i2 == len(s3) \
            or (i1 < len(s1) and s1[i1] == s3[i1+i2] and isInterleaveRecursive(i1+1, i2)) \
            or (i2 < len(s2) and s2[i2] == s3[i1+i2] and isInterleaveRecursive(i1, i2+1))
        return isInterleaveRecursive()

Em ngồi ngẫm nghĩ mãi không hiểu tại sao bác nghĩ ra cách đệ quy này,
Vì cách em nghĩ là y hệt như đề bài ra, chỉ là làm ngắn string lại

Còn cách của bác nó mới tricky, nên em không biết các suy luận như nào

Giải thích hướng suy luận đoạn đệ quy thôi hén. Ta bắt đầu từ ví dụ:

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

Ta nhận thấy:

1. Ký tự đầu tiên của s3 = "a" chỉ có thể lấy từ ký tự đầu tiên của s1 hoặc s2
2. Nếu ký tự đầu tiên của cả s1 và s2 đều k phù hợp thì fail cmnr
3. Trong trường hợp trên, vì s1[0] = "a" là phù hợp. Nên ta phát triển tiếp
4. Ký tự thứ 2 của s3 chỉ có thể là s1[1] hoặc s2[0]. Nếu không có ai phù hợp thì vứt.
5. Tương tự, giá trị khả thi của s3[2] chỉ có thể là s1[3] hoặc s2[0]
6. Vậy là khi ta xét đến một s3[k] nào đó, thì ta chỉ quan tâm s1 và s2 tại các vị trí i, j nào đó tùy vào các lựa chọn trước. Sau đó i, j sẽ thay đổi tăng 1 hoặc giữ nguyên tương ứng, để xét cho trường hợp k + 1.
7. Hơn thế nữa: ta luôn có i + j = k. Vì khi xét k tăng lên 1 đơn vị, thì hoặc ta tăng i, hoặc ta tăng j tương ứng lên 1 đơn vị.

=> Đến đây thì ta nhận ra bản chất đệ quy của bài toán. Với vị trí thứ s3[k] ta sẽ có 2 lựa chọn:

• Hoặc s1 == s3[k = i + j] => Xét tiếp với (i + 1, j)
• Hoặc s2[j] == s3[k = i + j] => Xét tiếp với (i, j + 1)

Dĩ nhiên ban đầu k = i = j = 0. Thêm memo thành quy hoạch động.

 

[thuyduong2007]

vâng, chắc do vòng for nên nó chạy chậm, nhưng e ko hiểu cách giải của bác sao lại chạy đúng, giải thích như nào để có thể code ra như vậy bác

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        @cache
        def isInterleaveRecursive(i1 = 0, i2 = 0) ->bool:
            return i1 + i2 == len(s3) \
            or (i1 < len(s1) and s1[i1] == s3[i1+i2] and isInterleaveRecursive(i1+1, i2)) \
            or (i2 < len(s2) and s2[i2] == s3[i1+i2] and isInterleaveRecursive(i1, i2+1))
        return isInterleaveRecursive()

Em ngồi ngẫm nghĩ mãi không hiểu tại sao bác nghĩ ra cách đệ quy này,
Vì cách em nghĩ là y hệt như đề bài ra, chỉ là làm ngắn string lại

Còn cách của bác nó mới tricky, nên em không biết các suy luận như nào

Dùng dp memo thì nhìn vấn đề theo kiểu top-down.
Giả sử:
s1 gồm các chữ cái a1, a2,...,an
s2 gồm các chữ cái b1, b2,...,bn
s3 gồm các chữ cái c1, c2,...,c3

Th1:
Nếu a1 == c1 thì khi đó mình sẽ đi giải bài toán ban đầu với kích thước nhỏ hơn
s1' gồm các chữ cái a2,...,an
s2 gồm các chữ cái b1, b2,...,bn
s3' gồm các chữ cái c2,...,c3
Th2:
Nếu b1 == c1 thì khi đó mình sẽ đi giải bài toán ban đầu với kích thước nhỏ hơn
s1 gồm các chữ cái a1,a2,...,an
s2' gồm các chữ cái b2,...,bn
s3' gồm các chữ cái c2,...,c3

Cách dùng index như t thì chỉ để optimize thôi.

Nếu ko dùng @cache thì tạo bảng memo (implement bằng tay) như nào bác, em thấy hơi ảo:

hàm isInterleaveRecursive nhận 2 số nguyên ví dụ isInterleaveRecursive(2,3)
thì có 2 case là s1 điền trước, s2 điền trước, mà chỉ có 1 cái đúng, cái kia sai, thì isInterleaveRecursive(2,3) = False sẽ skip hết các đệ quy phía sau,

chỗ đó dùng or mà, 1 cái đúng, 1 cái sai thì nó vẫn đúng chứ?

 

[Lập Trình Viên Số Khổ]

Hoặc s1 == s3[k = i + j] => Xét tiếp với (i + 1, j)

• Hoặc s2[j] == s3[k = i + j] => Xét tiếp với (i, j + 1)

Dĩ nhiên ban đầu k = i = j = 0. Thêm memo thành quy hoạch động.

sao chỗ này ko phải là s1[.i] == s3[k = i + j] => Xét tiếp với (i, j + 1) mà cứ phải (i+1,j) vậy bác

 

[Lập Trình Viên Số Khổ]

Dùng dp memo thì nhìn vấn đề theo kiểu top-down.
Giả sử:
s1 gồm các chữ cái a1, a2,...,an
s2 gồm các chữ cái b1, b2,...,bn
s3 gồm các chữ cái c1, c2,...,c3

Th1:
Nếu a1 == c1 thì khi đó mình sẽ đi giải bài toán ban đầu với kích thước nhỏ hơn
s1' gồm các chữ cái a2,...,an
s2 gồm các chữ cái b1, b2,...,bn
s3' gồm các chữ cái c2,...,c3
Th2:
Nếu b1 == c1 thì khi đó mình sẽ đi giải bài toán ban đầu với kích thước nhỏ hơn
s1 gồm các chữ cái a1,a2,...,an
s2' gồm các chữ cái b2,...,bn
s3' gồm các chữ cái c2,...,c3

Cách dùng index như t thì chỉ để optimize thôi.


chỗ đó dùng or mà, 1 cái đúng, 1 cái sai thì nó vẫn đúng chứ?

à giải thích thế này thì e dễ hiểu rùi bác, tks bác, đệ quy lằng nhằng thật. e update lại 1 cái bottom up

class Solution :
    def isInterleave(self, s1,  s2,  s3):
        
        if len(s3) != len(s1) + len(s2):
            return False
        
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]

        
        for i in range(0, len(s1) +1):
            for j in range(0, len(s2) + 1):
                if i == 0 and j == 0 :
                    dp[i][j] = True
                else :
                    dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
                
        return dp[len(s1)][len(s2)]

 

[tdat00]

Hôm nay lười mà thấy bài Hard với cái đề dài ngoẵng nữa. Thôi nay em bỏ đi cafe ngắm gái đây

Sent from Samsung SM-A528B using vozFApp

 

[NudeDuck]

Hard lòe người thôi chứ ý tưởng khá dễ bác ạ. Cơ mà phải submit 3 lần mới AC