バイナリ文字列ですべての 0 を 1 の前に配置するために必要な最小移動数

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃問題文＃＃＃

バイナリ文字列 str が与えられ、1 の前にすべての 0 を置くことができるように、文字列から最小数の文字を削除するように求められます。 ＃＃＃例＃＃＃ ＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

ここでは、2 つの方法で出力 3 を達成できます。

arr[2]、arr[3]、および arr[5]、または arr[4]、arr[6]、および arr[7] を文字列から削除できます。

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

イラスト

arr[4] と arr[6] を削除し、すべて 0 を 1 の前に置くことができます。

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

イラスト

指定された文字列では、すべてのゼロが 1 の前に配置されているため、指定された文字列から文字を削除する必要はありません。

方法1

最初の方法では、2 つの配列を使用します。最初の配列は左側にすべて 1 を格納し、もう一方の配列は右側にすべて 0 を格納します。その後、両方の配列の i 番目のインデックスに要素を追加し、最小の合計を見つけることができます。

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

ステップ 1

- 長さ n の「0」と「1」の名前付きリストを定義します。ここで、n は size() メソッドを使用して取得できる文字列の長さです。

ステップ 2

- 指定された文字列の最初の文字が「1」の場合は、「ones」配列の 0 番目のインデックスに 1 を格納し、それ以外の場合は 0 を格納します。

ステップ 3

- for ループを使用して、文字列の 2 番目の要素からトラバースを開始します。 for ループでは、Ones[i] は、インデックス i の文字列の文字に基づいて、Ones[i-1] を 1 または 0 に加算して得られる値で初期化されます。

ステップ 4

- 指定された文字列の最後の文字に応じて、Zeros[n-1] に 1 または 0 を格納します。

• ステップ 5

- for ループを使用して、最後から 2 番目の文字から文字列を走査し、文字列の文字に基づいてゼロ リストの値を更新します。

• ステップ 6
- 「min_zeros_to_remove」変数を定義し、最大の整数値で初期化します。

• ステップ 7
- 次に、「0」リストと「1」リストをループします。ゼロ リストの「i 1」インデックスと「1」リストの「I」インデックスから値にアクセスします。その後、これら 2 つの要素を追加します。

• ステップ 8
- 「min_zeros_to_remove」の値が「min_zeros_to_remove」変数の現在の値より小さい場合は、その値を 2 つの配列要素の合計に変更します。

• ステップ 9 - 結果の値を返します。

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

• 時間計算量

  - サイズ N の文字列とリストを反復するには for ループが必要なため、O(N)。

• 空間複雑度

  - 1 と 0 のカウントを保存するために 2 つのリストを使用するため、O(N)。

  方法 2

• この方法は、最初の方法の最適化バージョンです。ここでは、リストの代わりに 2 つの変数を使用して、1 と 0 の数を保存します。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

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

• ステップ 2

  - 文字列をループし、指定された文字列内の「0」文字の合計数をカウントし、それに応じて「zero_right」変数の値を更新します。

• ステップ 3

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

ステップ 4

- for ループを使用して文字列を反復処理します。文字列内のインデックス i の文字が「1」の場合、「ones_left」変数の値を 1 増やします。それ以外の場合は、「zeros_right」変数の値を 1 減らします。

ステップ 5

- 「zeros_right Ones_left」が「res」変数の現在の値より小さい場合は、「res」変数の値を更新します。

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

• 時間計算量

  - O(N)、文字列を反復処理する場合。

• 空間の複雑さ

  - 定数空間のみを使用するため、O(1)。

  ＃＃＃結論は＃＃＃
ユーザーは、指定されたバイナリ文字列から最小限の文字を削除する 2 つの方法を学習しました。 2 番目のアプローチのコードは、リストを使用する代わりに変数を使用して 0 と 1 の数を保存するため、より読みやすくなります。

以上がバイナリ文字列ですべての 0 を 1 の前に配置するために必要な最小移動数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。