2 番目のビットを繰り返し置換してバイナリ文字列を等しくします

この問題では、bin1 文字列の 2 番目の文字を最初と 2 番目の文字で置き換えることにより、bin1 文字列を bin2 文字列に変換する必要があります。 の最小値または最大値、および最初の文字が削除されます。

最初の文字を削除する必要があるため、2 つの文字列の最後の len2 − 1 文字が同じであることを確認する必要があります。さらに、bin1 文字列の開始文字に対して指定された操作を実行して、2 番目の文字列の最初の文字を取得できることを確認する必要があります。

問題文 - 長さ len1 および len2 の bin1 および bin2 バイナリ文字列が与えられています。次の操作で bin1 文字列を bin2 文字列に変換できるかどうかを確認する必要があります。

• bin1 文字列の最初と 2 番目の文字の最小値または最大値を使用して、bin1 文字列の 2 番目の文字を更新します。

• bin1 文字列の最初の文字を削除すると、文字列サイズは毎回 1 ずつ減ります。

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

手順- bin1 文字列を bin2 文字列に変換するには、次の手順を実行できます。

2 番目の文字を min(0,1) に置き換えて、最初の文字を削除できます。したがって、文字列は 001011 になります。

同じ操作をもう一度実行すると、文字列は 01011 になります。

次のいくつかの操作で、文字列はそれぞれ 0011 と 011 になります。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- 指定された文字列はすでに同じです。
• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- 指定された操作を実行して bin1 文字列を bin2 文字列に変換することはできません。

• 方法1

bin1 文字列の長さが短い場合、bin2 文字列に変換できません。

その他の場合、bin1 文字列の最後の len2 − 1 文字は、何も操作を実行しないため、変更されません。したがって、両方の文字列の最後の len2 − 1 文字は同じである必要があります。 さらに、bin2 文字列の最初の文字が '0' の場合、bin1 文字列の開始文字に対して min() 操作を実行する必要があり、少なくとも 1 つの '0' が含まれている必要があります。

bin2 文字列の最初の文字が '1' の場合、bin2 文字列の開始文字に対して max() 操作を実行する必要があり、その文字には少なくとも 1 つの '1' が含まれている必要があります。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

- bin1 の長さが bin2 文字列の長さより短い場合は、false を返します。

ステップ 2

- 2 番目の位置から開始して bin2 文字列をたどります。

ステップ 3

- bin2[p] が bin1[p len1 - len2] と等しくない場合は、最後の len2 -1 文字が同じではないため、false を返します。

ステップ 4

- 最初の len1 ～ len2 1 文字を調べて、bin2[0] 文字が含まれているかどうかを確認します。 「はい」の場合は、true を返します。

ステップ 5

- 関数の最後に false を返します。

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

時間計算量 - 文字列文字と一致する場合は O(N)。

動的空間を使用しないため、空間の複雑さ - O(1)。

指定された操作に従って、最初のバイナリ文字列を 2 番目のバイナリ文字列に変換する方法を学習しました。プログラマは、最後の文字を最後の文字と最後の 2 番目の文字の最小値または最大値に置き換え、最後の文字を削除することによって、ある文字列を別の文字列に変換できるかどうかをチェックしようとする場合があります。

以上が2 番目のビットを繰り返し置換してバイナリ文字列を等しくしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。