バイナリ文字列を別の文字列に変換するために必要なプレフィックス フリップの最小数

この問題では、最初のバイナリ文字列の接頭辞を反転して、最初のバイナリ文字列を 2 番目のバイナリ文字列に変換する必要があります。接頭辞の反転の最小数を取得するには、文字列の最後まで反復する必要があります。両方の文字列で一致しない文字が見つかった場合は、最初の文字列の接頭辞を反転する必要があります。

問題ステートメント-最初と二番目と呼ばれる2つの異なるバイナリ文字列が与えられます。 2 つのバイナリ文字列の長さは同じ N です。最初の文字列の接頭辞を反転して、最初の文字列を 2 番目の文字列に変換する必要があります。ここでは、ある文字列を別の文字列に変換するために必要なプレフィックス フリップの合計数を計算する必要があります。フリップとは、「0」を「1」に、「1」を「0」に変換することを意味します。

サンプル例

リーリー リーリー ＃＃＃説明＃＃＃

まず、最初の文字列の長さ 3 のプレフィックスを反転する必要があります。結果の文字列は 110 になります。
この後、長さ 2 のプレフィックスを反転する必要があります。結果の文字列は、2 番目の文字列と同じ 000 になります。

• リーリー リーリー ＃＃＃説明＃＃＃
長さ 2 のプレフィックスを反転する必要があり、結果の文字列は「01」となり、2 番目の文字列と等しくなります。

リーリー リーリー ＃＃＃説明＃＃＃

2 つの文字列は等しいため、反転する必要はありません。

アプローチ 1

このメソッドでは、文字列の末尾から反復処理を行い、一致しない文字が見つかった場合は、長さ「I 1」のプレフィックス内のすべての文字を反転します。これは問題を解決する簡単な方法です。

＃＃＃アルゴリズム＃＃＃

ステップ 1

- 変数「cnt」を定義し、0 に初期化します。

• ステップ 2

  -ループを使用して、文字列の最後からのトラバースを開始します。

  ステップ 3
-first[i] と Second[i] が等しくない場合は、長さが I 1 に等しいプレフィックスのすべての文字を反転する必要があります。

• #ステップ 4

  -ネスト for ループを使用して、I 1 に等しい長さのプレフィックスを反復処理し、flipBits() 関数を実行してその各文字を反転します。

• ステップ 4.1

  -flipBits() 関数で、現在の文字が「1」の場合は「0」を返し、現在の文字が「0」の場合は「1」を返します。

• ステップ 5-プレフィックスを反転するときに、「cnt」変数の値を 1 ずつ増やします。

• ステップ 6

  - 「cnt」変数の値を返します。

  ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
アプローチ 2

• このアプローチでは、各プレフィックス ビットを毎回反転するのではなく、「反転」変数を使用して現在のビットが反転したかどうかを追跡します。また、このアプローチではコードの時間計算量も最適化しました。＃＃＃アルゴリズム＃＃＃

#ステップ 1
• -「cnt」変数を定義し、「0」で初期化します。また、「inverted」変数を定義し、偽の値で初期化します。

ステップ 2

- 文字列を最後から順にたどります。最初の [i] 文字と 2 番目の [i] 文字が一致しない場合は、次の手順に従ってください。

ステップ2.1

-「inverted」の値が false の場合、「cnt」変数の値を 1 つ増やし、「inverted」変数の値を true に変更します.

ステップ 3
• -両方の文字が一致し、「inverted」の値が true の場合、ビットを再度反転する必要があるため、「cnt」の値を 1 ずつ増やします'inverted' の値を false に変更します。

  ＃＃＃例＃＃＃

  例を使用して、上記のアルゴリズムをデバッグしてみましょう。
リーリー

• 最初のステップでは、最初の [2] と 2 番目の [2] が一致せず、「inverted」の値は false です。したがって、「cnt」の値は１となり、「反転」が真となる。ここでは、「inverted」の値を true に変更することで、プレフィックスを仮想的に反転したと仮定します。

• その後、first[1] と Second[1] は一致しますが、「inverted」の値は true なので、「cnt」の値は 2 になり、「inverted」は false になります。 .
  次に、first[0] と Second[0] が一致し、「inverted」の値が false になるため、操作を実行する必要はありません。

• 最後に、値 2 を持つ「cnt」が返されます。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論＃＃＃

ある文字列を別の文字列に変換するために必要なプレフィックス反転の最小数を見つける 2 つの方法を学びました。ロジックは、文字列を末尾から反復処理し、一致しない文字が見つかった場合はプレフィックスを反転することです。

最初のアプローチのようにプレフィックスを反転するのではなく、「inverted」変数を使用して反転プレフィックスを追跡することで、時間計算量の観点から 2 番目のコードを最適化しました。

以上がバイナリ文字列を別の文字列に変換するために必要なプレフィックス フリップの最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。