Tuyên bố vấn đề
Cho một chuỗi nhị phân trong đó chúng ta có thể lật tất cả số 1 ở phần bên trái và tất cả số 0 ở phần bên phải. Nhiệm vụ là tính toán số lần lật tối thiểu cần thiết để làm cho tất cả số 1 ở bên trái và tất cả số 0 ở bên phải
Ví dụ
Cho chuỗi nhị phân là 0010101. Trong chuỗi này có 3 bit 1 và 4 bit 0. Chúng ta phải lật 4 bit được đánh dấu để làm cho tất cả 1 ở bên trái và tất cả 0 ở bên phải như hình dưới đây -
0010101
Sau khi lật chuỗi sẽ trở thành -
1110000
Thuật toán
- Duyệt chuỗi từ trái sang phải và tính số lần lật cần thiết để chuyển tất cả số 0 thành số 1.
- Lướt qua chuỗi từ phải sang trái và tính số lần lật cần thiết để che hết số 1 đến số 0
- Di chuyển qua tất cả các vị trí giữa các bit và tìm giá trị nhỏ nhất của (0 lần lật + 1 lần lật)
Ví dụ
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum flips: 4