thảo luận [Học Tập] Topic thuật toán

KimSoHyunGoddness said:

À vậy là phải lên leetcode đăng ký cái weekly contest thì mới đc phải ko

Click to expand...

_Gia_Cat_Luong_ said:

Tiếp tục chuyên mục mỗi ngày một leetcode. Các bài mình làm ngày hôm nay:

#378. (Medium) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix
#380. (Medium) https://leetcode.com/problems/insert-delete-getrandom-o1
#381. (Hard) https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed
#382. (Medium) https://leetcode.com/problems/linked-list-random-node
#383. (Easy) https://leetcode.com/problems/ransom-note

Mình sẽ share về bài Kth Smallest Element in a Sorted Matrix:
#378. (Medium) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

Phân tích bài toán:
Thật ra cũng k có gì mà phân tích cả, bài này giống hệt bài Find K Pairs with Smallest Sums mình đã share lần trước.
https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11114142

Solution:
Giống bài trước. Dùng heap. Idea tương tự đến 90%.

Python:

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix[0]), len(matrix)
        h = [(matrix[0][0], 0, 0)]
        visited = set([(0, 0)])
    
        while h:
            val, r, c = heappop(h)
            k -= 1
            if k <= 0:
                return val
        
            if r < m - 1 and (r + 1, c) not in visited:
                heappush(h, (matrix[r + 1][c], r + 1, c))
                visited.add((r + 1, c))
        
            if c < n - 1 and (r, c + 1) not in visited:
                heappush(h, (matrix[r][c + 1], r, c + 1))
                visited.add((r, c + 1))
            
        return None

Click to expand...

class Solution {
public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        int n = matrix.size(), l = matrix[0][0], r = matrix[n - 1][n - 1], m;
        while (true) {
            m = (l + r) / 2;
            int lo = 0, hi = 0;
            for (vector<int> &a:matrix) {
                lo += lower_bound(a.begin(), a.end(), m) - a.begin();
                hi += upper_bound(a.begin(), a.end(), m) - a.begin();
            }
            //m is (lo+1)-th to hi-th
            if (lo + 1 > k) r = m - 1;
            else if (hi < k) l = m + 1;
            else break;
        }
        return m;
    }
};

KimSoHyunGoddness said:

https://leetcode.com/problems/degree-of-an-array/
Cái bài này có thật là easy ko msây bác. Sao em thsây khó quá.
Chả lẻ em trình yếu thật sao

Click to expand...

• Tìm degree của array: Ví dụ degree = 2, có 2 số thỏa mãn là 1 và 2 (trong ví dụ).
• chuỗi con ngắn nhất thỏa mãn yêu cầu thực chất là dc tính từ first index tới last index của các số 1 và 2. Check xem first index và last index của 1, rồi 2, xem cái nào ngắn hơn thì đó là đáp án.
• first index và last index của 1 là 0 và 4-> độ dài là 5. Của 2 là 1 và 2 -> độ dài là 2 -> đáp án là 2!
• nums = [1,2,2,3,1]

KimSoHyunGoddness said:

https://leetcode.com/problems/degree-of-an-array/
Cái bài này có thật là easy ko msây bác. Sao em thsây khó quá.
Chả lẻ em trình yếu thật sao

Click to expand...

_Gia_Cat_Luong_ said:

Tiếp tục chuyên mục mỗi ngày một leetcode. Các bài mình làm ngày hôm nay:

#378. (Medium) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix
#380. (Medium) https://leetcode.com/problems/insert-delete-getrandom-o1
#381. (Hard) https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed
#382. (Medium) https://leetcode.com/problems/linked-list-random-node
#383. (Easy) https://leetcode.com/problems/ransom-note

Mình sẽ share về bài Kth Smallest Element in a Sorted Matrix:
#378. (Medium) https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

Phân tích bài toán:
Thật ra cũng k có gì mà phân tích cả, bài này giống hệt bài Find K Pairs with Smallest Sums mình đã share lần trước.
https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11114142

Solution:
Giống bài trước. Dùng heap. Idea tương tự đến 90%.

Python:

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix[0]), len(matrix)
        h = [(matrix[0][0], 0, 0)]
        visited = set([(0, 0)])
     
        while h:
            val, r, c = heappop(h)
            k -= 1
            if k <= 0:
                return val
         
            if r < m - 1 and (r + 1, c) not in visited:
                heappush(h, (matrix[r + 1][c], r + 1, c))
                visited.add((r + 1, c))
         
            if c < n - 1 and (r, c + 1) not in visited:
                heappush(h, (matrix[r][c + 1], r, c + 1))
                visited.add((r, c + 1))
             
        return None

Click to expand...

class Solution {
public:
    bool canConstruct(string r, string m) {
        int v[26] = {0};
      
        for(auto c:m) {
            v[c-'a']++;
        }
      
        for(auto c:r) {
            if (v[c-'a']-- <= 0) return false;
        }

        return true;
      
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& m, int k) {
    
        int n = m.size();

        int left = m[0][0], right = m[n-1][n-1], mid;
        while(left<=right)
        {
            mid = left + (right-left)/2;
            int count = 0;
                
            for(int i=0; i<n; i++)
            {
                count += upper_bound(m[i].begin(), m[i].end(), mid)- m[i].begin();          
            }
                      
            if(count < k)
                left = mid+1;
            else
                right = mid-1;
        }
      
      return right+1;
      
    }
};

Lập Trình Viên Số Khổ said:

View attachment 681267
Giải nhìu easy vào fen, nhìn tui giải 79 bài easy rùi nè

Click to expand...

KimSoHyunGoddness said:

Trên leetcode có nhiều bài có số dislike cao hơn số like. Thì thường là những bài đó ko được xếp đúng độ khó hay là ko áp dụng đc vào thực thế vậy mấy bác ?

Click to expand...

_Gia_Cat_Luong_ said:

Tiếp tục chuyên mục mỗi ngày một leetcode. 3 bài mình làm ngày hôm nay:

#375. (Medium) https://leetcode.com/problems/guess-number-higher-or-lower-ii/
#376. (Medium) https://leetcode.com/problems/wiggle-subsequence/
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

Mình sẽ share về bài Combination Sum IV:
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

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

• 1 <= nums.length <= 200: Với limit nhỏ như thế này thì có 2 khả năng:
  • Hoặc là độ phức tạp để giải rất cao O(2^n) hoặc thậm chí là O(n!)
  • Hoặc là kết quả output rất lớn. Nên nếu để limit quá cao sẽ bị tràn số
• Để biết là dạng nào thì ta có thể thử chạy test với input lớn một tí:
  • Nếu chạy lâu và ra kết quả là một số nhỏ => Trường hợp 1. Lúc này giải pháp tối ưu có lẽ là vét cạn. Các thuật toán phù hợp thường là liệt kê hoặc quay lui.
  • Nếu chạy nhanh nhưng ra kết quả là một số rất lớn => Trường hợp 2. Lúc này hướng giải thì hên xui, nhưng hay gặp nhất chắc là quy hoạch động.
• Quay lại bài này, ta thấy chỉ cần tăng input lên hơi to một chút là gặp ngay lỗi:

• => Có vẻ là hướng thứ 2, vậy ta thử giải bài này bằng QHĐ

Một chút về Quy Hoạch Động:

• Mình biết với nhiều người thuật toán QHĐ là một cái gì đó cao siêu, và dường như chỉ có các bậc thánh nhân chuyên tin mới nghĩ ra cách giải.
• Cách đây 1 năm mình cũng nghĩ vậy. Nhưng sau một thời gian cày cuốc và làm quen với dạng bài này, thì mình thấy nó cũng k có gì quá cao siêu.
• Chỉ cần nắm vững hướng tư duy và pattern của nó thì có thể vận dụng trong hầu hết các trường hợp. (Dĩ nhiên trừ những bài quá khó - mình cũng bó tay và vào discuss để xem như mn thôi. Kakaka)
• Với bạn nào chưa quen thì mình suggest xem clip này về QHĐ. Đây cũng là clip giúp mình làm quen với thuật toán này:

• Về cơ bản, pattern của thuật toán QHĐ tương tự như đệ quy, hay chia để trị. Đó là kết quả của bàn toán lớn được tính từ kết quả của các bài toán con, và tiếp tục đệ quy như thế cho đến trường hợp cơ bản đã biết trước.
• Cần chú ý là một bài toán giải bằng QHĐ cần có 2 tính chất:
  • Các bài toán con phải gối nhau: Thì việc lưu lại kết quả của các bài toán con mới có ý nghĩa tối ưu. Không thì nó chỉ là chia để trị thôi.
  • Cấu trúc con tối ưu: Kết quả tối ưu của bài toán lớn phải tính được từ kết quả tối ưu của các bài toán con. Nếu không thì có lưu lại kết quả của bài toán con cũng vô nghĩa.

Quay lại bài toán, ta thử áp dụng cách tiếp cận QHĐ để giải bài này:

• Để đếm số lượng các combinations có tổng bằng target, ta có thể tính nó từ kết quả của bài toán con hay không ?
• Vậy bài toán con ở đây là gì ? Hiểu nôm na đó là bài toán tương tự như bài toán gốc, nhưng với input "nhỏ" hơn
• "Nhỏ" ở đây không nhất thiết là nhỏ hơn về mặt toán học. Mà là input đó "gần" với "trường hợp cơ bản" hơn.
• "Trường hợp cơ bản" có nghĩa là các trường hợp mà từ đó ta có thể suy ra kết quả ngay lập tức, không cần phải thực hiện việc đưa về bài toán nhỏ hơn nữa.
• Quay lại, trong trường hợp này, bài toán con có thể là:
  • Cũng với mảng input đó, nhưng target là một số nhỏ hơn
  • Vẫn target đó, nhưng input ít đi một / một vài phần tử
• Ở đây ta thấy một phần tử có thể được dùng lại nhiều lần, nên xem ra hướng thứ hai khó khả thi. Nếu follow theo hướng thứ nhất, "target thấp hơn" thì "trường hợp cơ bản" sẽ là gì. Ta cứ nghĩ đến các case đơn giản nhất ?

• Đào sâu thêm một chút thì ta có thể tổng quá hóa thành như thế này:

• Vậy đưa về bài toán nhỏ hơn như thế nào ? Cái này gọi là "công thức truy hồi" và theo mình cũng là phần khó nhất của một bài QHĐ. Làm được hay không là ở chỗ bạn phải nhìn ra công thức này.
• Với mình, cách đơn giản là cứ execute một ví dụ và cố gắng thử tính bài toán lớn từ kết quả bài toán nhỏ. Ví dụ nums = [1, 2, 3]; target = 4:
• Giả sử ta biết số cách tạo ra "target = 3" đi, liệu ta có thể áp dụng nó để tính cho "target = 4" ?
• Đương nhiên có thể, dễ thấy giả sử có n cách để tạo ra "target = 3", ta chỉ việc cộng 1 vào mỗi cách đó để tạo ra "target = 4". Vì có số 1 nằm trong mảng input.
• Ồ. Vậy tổng quát hóa lên, nếu ta biết được có n cách tạo ra "target = x" thì cũng sẽ có n cách để tạo ra "target = k", nếu như "k - x" có nằm trong mảng input.
• Nghĩ ngược lại có vẻ sẽ hay hơn. Ta tính luôn với mỗi số x nằm trong mảng input thì sẽ có thêm combinationSum(k - x) cách để tạo ra số k.
• Nhưng cũng cần chú ý thêm edge case, nếu x = k luôn thì sao, khi đó vẫn có 1 cách để tạo ra số k, là chọn chính nó. Nhưng combinationSum(k - x) sẽ trả về 0 (vì 0 < nums[0]). Thôi thì ta thêm exception cho case này vậy.
• Vậy kết quả là tổng các combinationSum(k - x) với mỗi x trong mảng input.

Solution:

• Mình thích sử dụ Memoization, vì thấy nó gần hơn với suy nghĩ tự nhiên của con người
• Sort lại nums, lưu mảng nums đã sort lại
• Viết hàm đệ quy countCombination để tính
• Nếu target == 0: return 1
• Nếu target < nums[0]: return 0
• Nếu k == nums[0]: return 1
• Nếu target này đã được tính trước đó (nằm trong bảng kết quả), trả kết quả đã tính từ trước
• Tính kết quả bằng tổng các countCombination(k - x) với mỗi x trong mảng input.
• Lưu kết quả lại vào bảng kết quả, chú ý đây là bước quan trọng và thể hiện bản chất của quy hoạch động
• Trả về kết quả đã tính toán

Python:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        self.nums = nums
        return self.countCombination(target, {})
   
    def countCombination(self, target, memo):
        if target == 0:
            return 1
        if target < self.nums[0]:
            return 0
        if target == self.nums[0]:
            return 1
       
        if target in memo:
            return memo[target]
       
        memo[target] = sum(self.countCombination(target - x, memo) for x in self.nums)
        return memo[target]

p/s: Bài này thật ra khá kinh điển. Mình cố ý chọn nó và viết chi tiết để các bạn mới có thể học được cách tư duy và hướng phát triển vấn đề, thay vì chỉ đưa solution. Đồng thời solution bên trên chỉ đạt mức "faster than 11%". Nghĩa là còn có nhiều điểm có thể tối ưu cũng như viết gọn lại. Các bạn cứ đóng góp thoải mái. Welcome.

Click to expand...

KimSoHyunGoddness said:

View attachment 681625
Em mới giải thêm được bài nà.Đơn giản, suy luận chút là ra đáp án mà không hiểu sao tụi nó dislike bài này nhiều thế nhỉ.

Click to expand...

socola_smile said:

Làm thế nào cải thiện để trình bày được tốt như bác nhỉ


via theNEXTvoz for iPhone

Click to expand...

_Gia_Cat_Luong_ said:

Ngược lại thì đúng hơn bác ơi, mình trình bày khá kém. Một trong những nguyên nhân mình post mỗi ngày là để cải thiện khả năng trình bày của bản thân. Vì lúc phỏng vấn mình k chỉ cần phải code mà còn phải giải thích cái suy nghĩ của mình cho interviewer nữa.
Nên nếu bác muốn cải thiện thì mình suggest cứ viết ra như mình. Mỗi ngày làm một bài nào đó vừa tầm, rồi viết ra cách mình tiếp cận vấn đề và các bước mình xây dựng solution. Vừa cải thiện bản thân, vừa chia sẻ với mọi người.

Click to expand...

socola_smile said:

Làm thế nào cải thiện để trình bày được tốt như bác nhỉ


via theNEXTvoz for iPho

Click to expand...

_Gia_Cat_Luong_ said:

Tiếp tục chuyên mục mỗi ngày một leetcode. 3 bài mình làm ngày hôm nay:

#375. (Medium) https://leetcode.com/problems/guess-number-higher-or-lower-ii/
#376. (Medium) https://leetcode.com/problems/wiggle-subsequence/
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

Mình sẽ share về bài Combination Sum IV:
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

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

• 1 <= nums.length <= 200: Với limit nhỏ như thế này thì có 2 khả năng:
  • Hoặc là độ phức tạp để giải rất cao O(2^n) hoặc thậm chí là O(n!)
  • Hoặc là kết quả output rất lớn. Nên nếu để limit quá cao sẽ bị tràn số
• Để biết là dạng nào thì ta có thể thử chạy test với input lớn một tí:
  • Nếu chạy lâu và ra kết quả là một số nhỏ => Trường hợp 1. Lúc này giải pháp tối ưu có lẽ là vét cạn. Các thuật toán phù hợp thường là liệt kê hoặc quay lui.
  • Nếu chạy nhanh nhưng ra kết quả là một số rất lớn => Trường hợp 2. Lúc này hướng giải thì hên xui, nhưng hay gặp nhất chắc là quy hoạch động.
• Quay lại bài này, ta thấy chỉ cần tăng input lên hơi to một chút là gặp ngay lỗi:

• => Có vẻ là hướng thứ 2, vậy ta thử giải bài này bằng QHĐ

Một chút về Quy Hoạch Động:

• Mình biết với nhiều người thuật toán QHĐ là một cái gì đó cao siêu, và dường như chỉ có các bậc thánh nhân chuyên tin mới nghĩ ra cách giải.
• Cách đây 1 năm mình cũng nghĩ vậy. Nhưng sau một thời gian cày cuốc và làm quen với dạng bài này, thì mình thấy nó cũng k có gì quá cao siêu.
• Chỉ cần nắm vững hướng tư duy và pattern của nó thì có thể vận dụng trong hầu hết các trường hợp. (Dĩ nhiên trừ những bài quá khó - mình cũng bó tay và vào discuss để xem như mn thôi. Kakaka)
• Với bạn nào chưa quen thì mình suggest xem clip này về QHĐ. Đây cũng là clip giúp mình làm quen với thuật toán này:

• Về cơ bản, pattern của thuật toán QHĐ tương tự như đệ quy, hay chia để trị. Đó là kết quả của bàn toán lớn được tính từ kết quả của các bài toán con, và tiếp tục đệ quy như thế cho đến trường hợp cơ bản đã biết trước.
• Cần chú ý là một bài toán giải bằng QHĐ cần có 2 tính chất:
  • Các bài toán con phải gối nhau: Thì việc lưu lại kết quả của các bài toán con mới có ý nghĩa tối ưu. Không thì nó chỉ là chia để trị thôi.
  • Cấu trúc con tối ưu: Kết quả tối ưu của bài toán lớn phải tính được từ kết quả tối ưu của các bài toán con. Nếu không thì có lưu lại kết quả của bài toán con cũng vô nghĩa.

Quay lại bài toán, ta thử áp dụng cách tiếp cận QHĐ để giải bài này:

• Để đếm số lượng các combinations có tổng bằng target, ta có thể tính nó từ kết quả của bài toán con hay không ?
• Vậy bài toán con ở đây là gì ? Hiểu nôm na đó là bài toán tương tự như bài toán gốc, nhưng với input "nhỏ" hơn
• "Nhỏ" ở đây không nhất thiết là nhỏ hơn về mặt toán học. Mà là input đó "gần" với "trường hợp cơ bản" hơn.
• "Trường hợp cơ bản" có nghĩa là các trường hợp mà từ đó ta có thể suy ra kết quả ngay lập tức, không cần phải thực hiện việc đưa về bài toán nhỏ hơn nữa.
• Quay lại, trong trường hợp này, bài toán con có thể là:
  • Cũng với mảng input đó, nhưng target là một số nhỏ hơn
  • Vẫn target đó, nhưng input ít đi một / một vài phần tử
• Ở đây ta thấy một phần tử có thể được dùng lại nhiều lần, nên xem ra hướng thứ hai khó khả thi. Nếu follow theo hướng thứ nhất, "target thấp hơn" thì "trường hợp cơ bản" sẽ là gì. Ta cứ nghĩ đến các case đơn giản nhất ?

• Đào sâu thêm một chút thì ta có thể tổng quá hóa thành như thế này:

• Vậy đưa về bài toán nhỏ hơn như thế nào ? Cái này gọi là "công thức truy hồi" và theo mình cũng là phần khó nhất của một bài QHĐ. Làm được hay không là ở chỗ bạn phải nhìn ra công thức này.
• Với mình, cách đơn giản là cứ execute một ví dụ và cố gắng thử tính bài toán lớn từ kết quả bài toán nhỏ. Ví dụ nums = [1, 2, 3]; target = 4:
• Giả sử ta biết số cách tạo ra "target = 3" đi, liệu ta có thể áp dụng nó để tính cho "target = 4" ?
• Đương nhiên có thể, dễ thấy giả sử có n cách để tạo ra "target = 3", ta chỉ việc cộng 1 vào mỗi cách đó để tạo ra "target = 4". Vì có số 1 nằm trong mảng input.
• Ồ. Vậy tổng quát hóa lên, nếu ta biết được có n cách tạo ra "target = x" thì cũng sẽ có n cách để tạo ra "target = k", nếu như "k - x" có nằm trong mảng input.
• Nghĩ ngược lại có vẻ sẽ hay hơn. Ta tính luôn với mỗi số x nằm trong mảng input thì sẽ có thêm combinationSum(k - x) cách để tạo ra số k.
• Nhưng cũng cần chú ý thêm edge case, nếu x = k luôn thì sao, khi đó vẫn có 1 cách để tạo ra số k, là chọn chính nó. Nhưng combinationSum(k - x) sẽ trả về 0 (vì 0 < nums[0]). Thôi thì ta thêm exception cho case này vậy.
• Vậy kết quả là tổng các combinationSum(k - x) với mỗi x trong mảng input.

Solution:

• Mình thích sử dụ Memoization, vì thấy nó gần hơn với suy nghĩ tự nhiên của con người
• Sort lại nums, lưu mảng nums đã sort lại
• Viết hàm đệ quy countCombination để tính
• Nếu target == 0: return 1
• Nếu target < nums[0]: return 0
• Nếu k == nums[0]: return 1
• Nếu target này đã được tính trước đó (nằm trong bảng kết quả), trả kết quả đã tính từ trước
• Tính kết quả bằng tổng các countCombination(k - x) với mỗi x trong mảng input.
• Lưu kết quả lại vào bảng kết quả, chú ý đây là bước quan trọng và thể hiện bản chất của quy hoạch động
• Trả về kết quả đã tính toán

Python:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        self.nums = nums
        return self.countCombination(target, {})
  
    def countCombination(self, target, memo):
        if target == 0:
            return 1
        if target < self.nums[0]:
            return 0
        if target == self.nums[0]:
            return 1
      
        if target in memo:
            return memo[target]
      
        memo[target] = sum(self.countCombination(target - x, memo) for x in self.nums)
        return memo[target]

p/s: Bài này thật ra khá kinh điển. Mình cố ý chọn nó và viết chi tiết để các bạn mới có thể học được cách tư duy và hướng phát triển vấn đề, thay vì chỉ đưa solution. Đồng thời solution bên trên chỉ đạt mức "faster than 11%". Nghĩa là còn có nhiều điểm có thể tối ưu cũng như viết gọn lại. Các bạn cứ đóng góp thoải mái. Welcome.

Click to expand...