この問題では、最初のバイナリ文字列の接頭辞を反転して、最初のバイナリ文字列を 2 番目のバイナリ文字列に変換する必要があります。接頭辞の反転の最小数を取得するには、文字列の最後まで反復する必要があります。両方の文字列で一致しない文字が見つかった場合は、最初の文字列の接頭辞を反転する必要があります。
問題ステートメント-最初と二番目と呼ばれる2つの異なるバイナリ文字列が与えられます。 2 つのバイナリ文字列の長さは同じ N です。最初の文字列の接頭辞を反転して、最初の文字列を 2 番目の文字列に変換する必要があります。ここでは、ある文字列を別の文字列に変換するために必要なプレフィックス フリップの合計数を計算する必要があります。フリップとは、「0」を「1」に、「1」を「0」に変換することを意味します。
アプローチ 1
- 変数「cnt」を定義し、0 に初期化します。
-ループを使用して、文字列の最後からのトラバースを開始します。
ステップ 3#ステップ 4
-ネスト for ループを使用して、I 1 に等しい長さのプレフィックスを反復処理し、flipBits() 関数を実行してその各文字を反転します。ステップ 4.1
-flipBits() 関数で、現在の文字が「1」の場合は「0」を返し、現在の文字が「0」の場合は「1」を返します。ステップ 5-プレフィックスを反転するときに、「cnt」変数の値を 1 ずつ増やします。
- 「cnt」変数の値を返します。
###例### リーリー ###出力### リーリーこのアプローチでは、各プレフィックス ビットを毎回反転するのではなく、「反転」変数を使用して現在のビットが反転したかどうかを追跡します。また、このアプローチではコードの時間計算量も最適化しました。###アルゴリズム###
###例###
例を使用して、上記のアルゴリズムをデバッグしてみましょう。最初のステップでは、最初の [2] と 2 番目の [2] が一致せず、「inverted」の値は false です。したがって、「cnt」の値は1となり、「反転」が真となる。ここでは、「inverted」の値を true に変更することで、プレフィックスを仮想的に反転したと仮定します。
次に、first[0] と Second[0] が一致し、「inverted」の値が false になるため、操作を実行する必要はありません。
最後に、値 2 を持つ「cnt」が返されます。
以上がバイナリ文字列を別の文字列に変換するために必要なプレフィックス フリップの最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。