_Gia_Cat_Luong_
Senior Member
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:
#399. (Medium) https://leetcode.com/problems/evaluate-division
#400. (Medium) https://leetcode.com/problems/nth-digit
#401. (Easy) https://leetcode.com/problems/binary-watch
#402. (Medium) https://leetcode.com/problems/remove-k-digits
Mình sẽ share về bài Remove K Digits:
#402. (Medium) https://leetcode.com/problems/remove-k-digits
Phân tích bài toán:
Dĩ nhiên solution này không work, vì nó còn gặp nhiều vấn đề:
Giải thuật tham lam (greedy):
Các vấn đề khác
Ta sẽ cần suy nghĩ, bổ sung thêm các logic để xử lý các trường hợp này. Việc tự nghĩ ra các edge cases cũng là một kỹ năng quan trọng trong việc coding.
Solution:
#399. (Medium) https://leetcode.com/problems/evaluate-division
#400. (Medium) https://leetcode.com/problems/nth-digit
#401. (Easy) https://leetcode.com/problems/binary-watch
#402. (Medium) https://leetcode.com/problems/remove-k-digits
Mình sẽ share về bài Remove K Digits:
#402. (Medium) https://leetcode.com/problems/remove-k-digits
Phân tích bài toán:
- 1 <= k <= num.length <= 10^5: Độ phức tạp kỳ vọng có thể là O(n) hoặc tệ lắm thì là O(nlogn)
- Đầu tiên dễ thấy trong trường hợp bình thường, nếu chuỗi ban đầu có n số, thì sau khi bỏ đi k chữ số. Chuỗi kết quả sẽ có (n - k) chữ số.
- Vậy với một chuỗi cố định có (n - k) số. Ta sẽ làm thế nào để có kết quả nhỏ nhất ?
- Ý tưởng hiển nhiên là ta sẽ chọn sao cho số nhỏ đứng trước - số lớn đứng sau.
- Hay nói cách khác, nếu số đứng sau mà nhỏ hơn số đứng trước, thì số đứng trước phải bị bỏ đi
- Tại đây ta có thể xây dựng một thuật toán naive như sau:
Python:
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
res = []
for n in num:
while res and res[-1] > n:
res.pop()
res.append(n)
return ''.join(res)Dĩ nhiên solution này không work, vì nó còn gặp nhiều vấn đề:
Giải thuật tham lam (greedy):
- Vấn đề đầu tiên của solution trên là nó mang tính "greedy". Nghĩa là nó chỉ "giải" theo mục tiêu trước mắt, chứ k quan tâm đến mục tiêu toàn cục.
- Trong đoạn code trên, hễ gặp số trước lớn hơn số sau thì ta loại nó ngay. Nhưng vì ta chỉ có thể loại k phần tử, ta cần cân nhắc rằng sau này có thể có những số khác xuất hiện, khiến cho việc "giữ lại" số này sẽ có lợi hơn là loại bỏ nó ngay lập tức.
- May mắn thay với bài này thì không như vậy, việc loại phần tử ngay lập tức vẫn tối ưu cho trường hợp toàn cục. Các bạn có thể tự suy nghĩ xem tại sao.
- Tuy nhiên ta cần hiểu rằng không phải bài toán nào cũng có tính chất này, và ta cần phải cẩn thận mỗi khi sử dụng những solution có tính "greedy" như trên.
Các vấn đề khác
- Solution trên có thể remove nhiều hơn k phần tử
- Hoặc có thể remove ít hơn k phần tử
- Trường hợp leading zero thì sao ?
- Nếu các số bị bỏ hết thì thế nào ?
Ta sẽ cần suy nghĩ, bổ sung thêm các logic để xử lý các trường hợp này. Việc tự nghĩ ra các edge cases cũng là một kỹ năng quan trọng trong việc coding.
Solution:
- Với mỗi chữ số trong num
- Nếu chữ số đứng trước còn lớn hơn chữ số hiện tại:
- Bỏ chữ số đứng trước đi (nhưng tối đa k lần thôi)
- Nếu không phải leading zerio thì thêm chữ số hiện tại vào kết quả
- Nếu chữ số đứng trước còn lớn hơn chữ số hiện tại:
- Nếu chưa loại đủ k ký tự thì loại các ký tự ở cuối cho đủ k (why??)
- Trả về kết quả, cần để ý trường hợp empty
Python:
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
res = []
for n in num:
while k > 0 and res and res[-1] > n:
res.pop()
k -= 1
if res or n != '0':
res.append(n)
if k > 0:
res = res[:-k]
if not res:
return '0'
return ''.join(res)
Sửa lần cuối:
