最小のオペランドで 1 ビットを除くすべてのビットを反転して、指定されたバイナリ文字列を別のバイナリ文字列に変換します。

この問題では、文字列の文字を反転して、あるバイナリ文字列を別のバイナリ文字列に変換する必要があります。設定されたビットを保存し、他のビットを反転することができます。これを行うことで、別の文字列を実装するための合計操作を計算する必要があります。

指定された文字列内の「01」と「10」のペアの合計数に基づいて問題を解くことができます。

問題文- バイナリ文字列を表す、「0」と「1」の文字を含む、str1 と str2 という同じ長さの 2 つの文字列が与えられています。次の手順を実行して、文字列 str1 を str2 に変換する必要があります。

• 任意の設定ビットを選択し、他のすべてのビットを反転できます。ビットの反転とは、「0」を「1」に、「1」を「0」に変換することを意味します。

• str1 を str2 に変換できない場合は、-1 を出力します。

＃＃＃例＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明

-

最初の操作では、2 番目のインデックスの「1」を変更せずに保持し、str1 内の他のすべての文字を反転します。したがって、str1 は 111110000 になります。

2 番目の操作では、インデックス 0 の「1」を変更せずに保持し、他のすべての文字を反転します。したがって、str1 は 100001111 になります。

最後の操作では、5 番目のインデックスに「1」を保存します。したがって、str1 は 011111000 になります。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
• 説明

  - str1 には保存する「1」文字が含まれていないため、str1 を str2 に変換できません。

  ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
• 説明

  - str1 を str2 に変換できません。

方法1

観察を通じて問題を解決できます。観察によれば、任意の 1 つのセットビットを保持して 2 つの操作を実行すると、同じ文字列が得られることがわかります。したがって、文字列を変更するには、別の 1 インデックスを選択する必要があります。 また、01 のペアを 10 に変換するには 2 つの操作を実行する必要があります。たとえば、「01」は「1」のままにします。したがって、「11」が得られます。その後、「11」の 0 番目のインデックスを「1」のままにして、「10」を取得します。

答えを得るには、01 (0 -> str1、1 -> str2) と 10 (1 -> str1、0 -> str2) が同じである必要があります。そうでなければ、答えは存在しないと言えます。 「01」を「10」に 2 回の操作で変換できるため、主な目標は「01」と「10」のペアを最小限に抑えることです。

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

ステップ 1- totalOperatrions() 関数を定義して、str1 を str2 に変換するために必要な操作の数を計算します。

ステップ 1.2 - count10 変数と count01 変数を初期化して、「01」と「10」のペアを文字列に格納します。

ステップ 1.3 - 文字列をループし、両方の文字列の 01 と 10 のペアを数えます。

ステップ 1.4- count10 と count01 が同じ場合、2*count10 を返します。それ以外の場合は、-1 が返されます。

ステップ 2

- minimumOperations() 関数を定義して、str1 を str2 に変換するために必要な最小限の操作を計算します。

ステップ 3

- 「ans」を最大値で初期化します。

ステップ 4

- 元の文字列を使用して totalOperations() 関数を呼び出し、結果を「operation1」変数に保存します。戻り値が -1 に等しくない場合、ans と演算 1 の最小値が ans に格納されます。

ステップ 5- 次に、01 と 10 のペアを最小化するように文字列を変更します。したがって、stringModification()関数を定義します。

ステップ 5.1 - この関数では、文字列内の「1ch」の最初のペアを見つけて、パラメータとして「ch」を渡します。これは「0」または「1」です。したがって、ペアは 1 -> str1 および ch -> str のようになります。

ステップ 5.2- 「1ch」ペアが見つからない場合は、false を返します。

ステップ 5.3 - 「1ch」ペアが見つかった場合は、そのペアを変更せずに維持し、str1 の他の文字を反転します。

ステップ 6 - stringModification 関数を実行して、「11」のペアを変更せずに維持し、他の文字を反転します。その後、 totalOperations() 関数が再度呼び出され、str1 を str2 に変換するために必要な操作が検索されます。

ステップ 7- 操作 2 が -1 に等しくない場合は、「ans」に最小値を格納するか、「ans」に「1 操作 2」を格納します。ここでは、1 回の操作で文字列を変更したため、1 を追加しました。

ステップ 8 - 最初の「10」ペアを変更しないで文字列を変更し、オペランドを計算します。再度、最小値を「ans」に代入します。

ステップ 9- 「ans」が INT_MAX に等しい場合、-1 を返します。それ以外の場合は、ans を返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量- O(N)。stringModification() 関数と totalOperations() 関数で文字列を反復処理するためです。

スペースの複雑さ- O(1)。余分なスペースを使用せずに同じ文字列を変更するためです。

コードの主な目的は、文字列を変更して操作を最小限に抑えた後、指定された文字列内の 01 と 10 のペアの数を減らすことです。プログラマーはさまざまな入力を使用して、答えを理解しようとします。

以上が最小のオペランドで 1 ビットを除くすべてのビットを反転して、指定されたバイナリ文字列を別のバイナリ文字列に変換します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。