Remove K Digits

Q: Độ phức tạp thời gian của Remove K Digits là gì?

Với ngăn xếp đơn điệu, thuật toán chạy trong thời gian O(n) với n chữ số: mỗi chữ số được đưa vào ngăn xếp một lần, và mỗi lần lấy ra sử dụng một trong k lượt xóa. Ngăn xếp chứa tối đa n chữ số, vì vậy bộ nhớ phụ là O(n) . Quét lại từ trái sang phải cho mỗi lượt xóa tốn O(n·k) .

Trung bìnhNgăn xếp đơn điệu Tham lam

+10

Bạn nhận được một số không âm được viết dưới dạng chuỗi chữ số, num, và một số nguyên k. Hãy xóa chính xác k chữ số và giữ lại các chữ số còn lại theo đúng thứ tự ban đầu, sao cho số còn lại nhỏ nhất có thể.

Trả về số đó dưới dạng chuỗi không có số 0 ở đầu. Nếu không còn chữ số nào hoặc chỉ còn các số 0, hãy trả về "0".

Hàm

removeKdigits(num: string, k: integer) → string

numstring: số đó, được viết dưới dạng một chuỗi chữ số
kinteger: cần xóa bao nhiêu chữ số
Trả vềstring: số nhỏ nhất bạn có thể để lại, dưới dạng chuỗi không có số 0 ở đầu

Ràng buộc

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num chỉ chứa các chữ số từ 0 đến 9.
num không có số 0 ở đầu, trừ khi chính nó là số 0, "0".

Ví dụ

Đầu vào: num = "4325043"k = 3
Đầu ra: "2043"
Giải thích: Bỏ số 4 và số 3 đầu tiên sẽ đưa số 2 lên trước. Số 0 không thể đứng đầu: có bốn chữ số đứng trước nó và bạn được xóa ba chữ số. Lần xóa cuối cùng lấy số 5, vì nó đứng trước một số 0 nhỏ hơn.

Đầu vào: num = "30200"k = 1
Đầu ra: "200"
Giải thích: Bỏ chữ số 3 sẽ còn lại 0200, và khi bỏ số 0 ở đầu, ta có 200. Bỏ bất kỳ chữ số nào khác vẫn giữ chữ số 3 ở đầu và cho ra một số có bốn chữ số, chẳng hạn như 3000.

Đầu vào: num = "52"k = 2
Đầu ra: "0"
Giải thích: Cả hai chữ số đều bị xóa, vì vậy không còn gì và đáp án là "0".

Câu hỏi mở rộng

Bạn sẽ thay đổi lời giải như thế nào để xóa k chữ số và giữ lại số lớn nhất?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Các chữ số ở ngoài cùng bên trái có giá trị lớn nhất, vì vậy chữ số đầu tiên lớn hơn chữ số bên phải nó cần được loại bỏ. Một ngăn xếp chứa các chữ số được giữ lại sẽ áp dụng quy tắc đó cho toàn bộ chuỗi chỉ trong một lượt. Những chữ số cần loại bỏ còn lại sẽ bị xóa từ cuối, sau đó mới loại bỏ các số 0 ở đầu.

Xóa từng chữ số một

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Xóa từng chữ số một: tìm vị trí đầu tiên i sao cho num[i] > num[i+1] rồi xóa num[i], hoặc xóa chữ số cuối cùng nếu các chữ số không bao giờ giảm. Lặp lại k lần.

Mỗi đáp án giữ lại n-k chữ số, vì vậy vị trí đầu tiên mà hai đáp án khác nhau sẽ quyết định đáp án nào nhỏ hơn. Từ đầu đến i, các chữ số không bao giờ giảm, nên xóa một chữ số trước đó sẽ đưa vào vị trí ấy một chữ số lớn hơn hoặc bằng; xóa một chữ số sau đó thì vẫn giữ nguyên chữ số lớn num[i]. Xóa num[i] làm giảm chữ số sớm nhất có thể giảm.

Mỗi lần xóa đều quét lại từ trái sang phải và dịch các chữ số phía sau, nên độ phức tạp là O(n·k). Với 40,000 chữ số 1 và k = 25,000, các lượt quét đọc khoảng 6.9 × 10^8 chữ số.

Thuật toán

Sao chép các chữ số vào một danh sách (list) mà bạn có thể xóa phần tử.
Lặp lại k lần: đi từ trái sang phải đến chữ số đầu tiên lớn hơn chữ số tiếp theo, hoặc đến chữ số cuối cùng, rồi xóa chữ số đó.
Xóa các số 0 ở đầu và trả về "0" nếu không còn gì.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Ngăn xếp đơn điệu chứa các chữ số được giữ lại

Ý tưởng

Sau khi phiên bản chậm xóa num[i], các chữ số đứng trước i vẫn không bao giờ giảm, nên lần xóa tiếp theo chỉ có thể bắt đầu ở chữ số ngay trước khoảng trống. Ngăn xếp lưu phần tiền tố đó: các chữ số được giữ lại, không giảm dần từ đáy lên đỉnh. Khi chữ số mới nhỏ hơn chữ số trên đỉnh, chữ số trên đỉnh lớn hơn chữ số bên phải nó, tức chữ số mà phiên bản chậm sẽ xóa. Hãy lấy chữ số đó ra, dùng một lượt xóa và tiếp tục lấy ra khi chữ số mới trên đỉnh vẫn lớn hơn.

Với 4325043 và k = 3, chữ số 3 khiến chữ số 4 bị lấy ra, chữ số 2 khiến chữ số 3 bị lấy ra, còn chữ số 0 khiến chữ số 5 bị lấy ra. Chữ số 4 và chữ số 3 được đẩy vào ngăn xếp khi lần lượt xuất hiện, tạo thành 2043.

Mỗi chữ số được đẩy vào ngăn xếp một lần và mỗi lần lấy ra sẽ dùng một trong k lượt xóa, nên lượt xử lý có độ phức tạp O(n).

Thuật toán

Tạo một ngăn xếp chữ số trống.
Với mỗi chữ số của num: khi vẫn còn lượt xóa và chữ số trên cùng của ngăn xếp lớn hơn chữ số đó, hãy lấy chữ số trên cùng ra và dùng hết một lượt xóa. Sau đó, đẩy chữ số đó vào ngăn xếp.
Nếu vẫn còn lượt xóa sau vòng lặp, hãy xóa số chữ số tương ứng từ trên cùng của ngăn xếp.
Đọc ngăn xếp từ dưới lên trên, bỏ qua các số 0 ở đầu và trả về phần còn lại, hoặc "0" nếu không còn gì.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Lỗi thường gặp và trường hợp biên

Lấy phần tử ra khi chữ số trên cùng bằng chữ số mới. Với 112 và k = 1, kết quả là 12; đáp án đúng là 11.
Quên xử lý số lần xóa còn lại sau vòng lặp, hoặc xóa từ đầu. Ngăn xếp không bao giờ giảm, nên các chữ số cuối của nó sẽ là: 123456789 với k = 3 cho kết quả 123456.
Tính các số 0 bị loại bỏ là số lần xóa. Với 100200 và k = 1, chữ số 1 là phần tử duy nhất bị xóa; các số 0 ở đầu được bỏ qua miễn phí, và đáp án là 200.
Trả về chuỗi rỗng. 10 với k = 1 chỉ còn lại số 0, nên đáp án là "0".
Chuyển num thành số nguyên. Nó có thể có 4 × 10^4 chữ số, vượt xa khả năng của mọi kiểu số nguyên, nên hãy so sánh các chữ số dưới dạng ký tự.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Remove K Digits là gì?

Với ngăn xếp đơn điệu, thuật toán chạy trong thời gian O(n) với n chữ số: mỗi chữ số được đưa vào ngăn xếp một lần, và mỗi lần lấy ra sử dụng một trong k lượt xóa. Ngăn xếp chứa tối đa n chữ số, vì vậy bộ nhớ phụ là O(n). Quét lại từ trái sang phải cho mỗi lượt xóa tốn O(n·k).

Bạn xử lý các số 0 đứng đầu trong Remove K Digits như thế nào?

Trước tiên, hãy xóa các chữ số rồi chỉ bỏ các số 0 ở cuối. Số 0 ở đầu không làm thay đổi giá trị, nên không tốn lượt xóa nào: 10200 với k = 1 trở thành 0200 rồi thành 200. Nếu không còn gì sau khi bỏ các số 0, hãy trả về "0".

Có thể giải bài toán Xóa K chữ số với O(1) bộ nhớ phụ không?

Có, nếu bạn có thể thay đổi đầu vào. Ngăn xếp không bao giờ chứa nhiều chữ số hơn số chữ số bạn đã đọc, vì vậy nó có thể nằm ngay ở phần đầu của mảng chữ số, với một chỉ số cho đỉnh ngăn xếp. Các ngôn ngữ có chuỗi bất biến vẫn cần một bản sao của các chữ số, với độ phức tạp O(n).

def removeKdigits(num, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

num = "4325043"
k = 3

Đầu ra mong đợi

"2043"