(by ndaadn)
Cho một chuỗi nhị phân và một số k, bạn được phép đổi nhiều nhất k số 0 thành số 1. Hãy trả lại độ dài lớn nhất của chuỗi số 1 liên tiếp mà bạn có thể tạo được.
Ví dụ:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Ta có thể đổi 2 số 0 thành số 1 như sau (số được gạch chân)
[1,1,1,0,0,1,1,1,1,1,1]
(by phucnh)
Trước hết ta cần xác định rằng: ta không thể sắp xếp lại mảng đầu vào. Ví dụ với mảng đầu vào như dưới đây, ta sẽ có kết quả hoàn toàn khác nếu thứ tự của các phần tử khác nhau.
original input = ["a", "a(1)", "a(2)", "a"]
output = ["a", "a(1)", "a(2)", "a(3)"]
Nếu ta thay đổi thứ tự của các phần tử, ta có kết quả như sau:
sorted input = ["a", "a", "a(1)", "a(2)"]
output = ["a", "a(1)", "a(1)(1)", "a(2)"]
Như vậy, để xác định xem tên thư mục đã được sử dụng hay chưa, ta có thể sử dụng Set. Nếu tên thư mục đã được sử dụng trước đó, ta tăng giá trị hậu tố lên một đơn vị, rồi tiến hành kiểm tra cho tới khi tên thư mục hoàn toàn mới. Ta có giả mã như sau:
https://pastebin.com/fNTxfKT1
Với giải thuật trên, trong trường hợp mảng đầu vào chỉ chứa một giá trị (ví dụ: tất cả phần tử đều là chữ cái “a”), giải thuật có độ phức tạp thời gian lên tới O(n^2 * S), với n là độ dài của mảng đầu vào, S là độ dài tối đa của một phần tử.
Độ phức tạp thời gian của giải thuật sẽ trở thành amortized O(n*S)
