Số lần lật bit tối thiểu để 1 ở bên trái, 0 ở bên phải trong C++

Đề bài

Cho chuỗi nhị phân, ta có thể lật tất cả 1 ở phần bên trái và tất cả 0 ở phần bên phải. Nhiệm vụ tính số lần lật tối thiểu để tất cả 1 ở trái và tất cả 0 ở phải.

Ví dụ

Cho chuỗi nhị phân 0010101. Có 3 bit 1 và 4 bit 0. Cần lật 4 bit nổi bật để có 1110000.

Thuật toán

• Duyệt chuỗi từ trái sang phải, đếm số lật cần để chuyển tất cả 0 thành 1.
• Duyệt từ phải sang trái, đếm số lật cần để chuyển tất cả 1 thành 0.
• Duyệt qua tất cả vị trí giữa các bit, tìm giá trị nhỏ nhất của (lật 0 + lật 1).

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 << "Số lần lật tối thiểu: " << minFlips(binaryString) << endl;
    return 0;
}

Kết quả

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:

Số lần lật tối thiểu: 4