バイナリ文字列を交互にするためのフリップの数-C++で1を設定します

バイナリ文字列「10011」を指定したとします。代替のバイナリ文字列を作成するには、「10101」として最低2文字を反転する必要があります。

代替文字列には2つの可能性があります。 0または1で始まります。2つの選択肢をチェックし、両方に必要なフリップの数を数えます。

そして、両方の最小値を返します。例を見てみましょう。

入力

binary = "10011"

出力

2

文字列を0で始める場合、3回反転する必要があります。また、文字列を1で始める場合は、2回反転する必要があります。最小値は2です。

アルゴリズム

• バイナリ文字列を初期化します。
• 1から始まる文字列を交互にするために必要なフリップを数えます。
• 同様に、0から始まる文字列を交互にするために必要なフリップを数えます。
• 上記の2つから最小値を見つけます。
• メニマムを印刷します。

実装

以下は、C++での上記のアルゴリズムの実装です

#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
   return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
   int flipCount = 0;
   for (int i = 0; i < binary.length(); i++) {
      if (binary[i] != expected) {
         flipCount++;
      }
      expected = flip(expected);
   }
   return flipCount;
}
int main() {
   string binary = "10011";
   cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary,       '1')) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

2