Lật tối thiểu để thực hiện tất cả các số 1 ở bên trái và số 0 ở bên phải trong C ++

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