C++ですべての1を左に、0を右に作成するための最小フリップ

問題の説明

左側のすべての1と右側のすべての0を反転できるバイナリ文字列があるとします。タスクは、すべて1を左に、すべて0を右にするために必要な最小フリップを計算することです

例

与えられたバイナリ文字列は0010101です。この文字列には、3つの1ビットと4つの0ビットがあります。以下に示すように、ハイライトされた4ビットを反転して、すべて1を左に、すべて0を右にする必要があります-

0010101

文字列を反転した後は-

1110000

アルゴリズム

• 文字列を左から右にトラバースし、すべての0を1に変換するために必要なフリップの数を計算します。
• 文字列を右から左にトラバースし、1から0まですべてを変換するために必要なフリップの数を計算します
• ビット間のすべての位置をトラバースして、（0のフリップ+ 1のフリップ）の最小値を見つけます

例

#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;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum flips: 4