Giả sử chúng ta có một chuỗi nhị phân đặc biệt. Chuỗi này có các tính chất sau −
Số lượng 0 và 1 bằng nhau
Mọi tiền tố trong chuỗi nhị phân đều có số 1 ít nhất bằng số 0
Bây giờ giả sử chúng ta có chuỗi đặc biệt S, một nước đi thực sự là chọn hai chuỗi con đặc biệt liên tiếp, không rỗng của S, và hoán đổi chúng.
Chúng ta phải tìm chuỗi kết quả lớn nhất theo thứ tự từ điển có thể có, sau bất kỳ số lượng nước đi nào.
Vì vậy, nếu đầu vào giống như 11011000, thì đầu ra sẽ là 11100100, điều này là do: Các chuỗi con "10" và "1100" được hoán đổi. Đây là chuỗi lớn nhất theo thứ tự từ điển có thể sau một vài nước đi.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa hàm makeLargestSpecial(), nhận s,
ret := chuỗi rỗng
Định nghĩa mảng v của các chuỗi
i := 0
for khởi tạo j := 0, cnt := 0, khi j < kích thước của s, cập nhật (tăng j lên 1), thực hiện −
nếu s[j] bằng '1', thì −
(tăng cnt lên 1)
Ngược lại
(giảm cnt xuống 1)
nếu cnt bằng 0, thì −
chèn "1" + makeLargestSpecial(chuỗi con của s từ chỉ số i + 1 đến j - i - 1) vào cuối v
i := j + 1
sắp xếp mảng v.r
for khởi tạo i := 0, khi i < kích thước của v, cập nhật (tăng i lên 1), thực hiện −
ret := ret + v[i]
trả về ret
Từ phương thức main gọi makeLargestSpecial() với chuỗi.
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: string makeLargestSpecial(string s) { string ret = ""; vector<string> v; int i = 0; for (int j = 0, cnt = 0; j < s.size(); j++) { if (s[j] == '1') { cnt++; } else cnt--; if (cnt == 0) { v.push_back("1" + makeLargestSpecial(s.substr(i + 1, j - i - 1)) + "0"); i = j + 1; } } sort(v.rbegin(), v.rend()); for (int i = 0; i < v.size(); i++) ret += v[i]; return ret; } }; main(){ Solution ob; cout << (ob.makeLargestSpecial("11011000")); } Đầu vào
11011000
Đầu ra
11100100