文字列を 0 の文字列とその後に続く 1 の文字列で構成するための最小削除数

質問「部分文字列が 0 個の文字列連結の最小削除数」には、文字列の操作が含まれます。入力として 0 と 1 の文字列を指定すると、結果は、連続する 0 の部分文字列を生成するために削除する必要がある 0 の最小数を反映する整数になります。

言い換えると、問題は次のように再定式化できます。0 と 1 で構成される文字列が与えられた場合、残りの文字列に連続した 0 の期間が含まれるようにするには、いくつの 0 を削除する必要があります。

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

ステップ 1: 変数の初期化

現在のゼロ シーケンスの長さを記録するカウント変数を定義します。
max_count 変数を定義して、これまでに検出された最長のゼロのシーケンスを追跡します。
両方の変数を 0 に設定します。
ステップ 2: 文字列のトラバーサル

ループを使用して、文字列内の各文字を反復処理します。

ステップ 3: ゼロ検出

現在の文字がゼロの場合、カウント変数をインクリメントします。

ステップ 4: 1 つの検出

現在の文字が 1 の場合、count 変数と max_count 変数を比較します。
count 変数が max_count 変数より大きい場合は、max_count 変数を count 変数と同じに設定します。
カウント変数を 0 にリセットします。
ステップ 5: ループの完了

文字列内のすべての文字が処理されるまで、このプロセスを繰り返します。

ステップ 6: 最小削除の計算

残りのゼロがゼロで区切られないようにすべてのゼロを削除するために必要な最小削除数は、文字列の長さから max_count を減算することで計算できます。

ステップ 7: 結果の出力

結果をコンソールに出力します。

従うべき方法

動的メソッド
反復方法
方法 1: 動的方法

動的プログラミングを使用すると、この問題を効率的に解決できます。連続する 0 の部分文字列を作成するには、配列 dp[] を作成します。ここで、dp[i] は、部分文字列 s[0...i] から削除する必要がある 0 の最小数を表します。空の部分文字列から削除する 0 の最小数は 0 であるため、dp[0] を 0 に初期化できます。

次に、文字列 s を反復処理して、dp[i] を −

に更新します。

s[i] が「0」の場合、連続する 0 の部分文字列に s[i] を含めることも、それらを削除することもできるため、dp[i] = dp[i-1] になります。
s[i] が "1" の場合、i に最も近いインデックス j を取得する必要があります。これには、連続する 0 の部分文字列が含まれます。これは、i-1 から 0 までを反復し、部分文字列 s[j...i] に連続した 0 が含まれているかどうかを確認することで実行できます。インデックス j が見つかった場合、dp[i] = dp[j-1] (i-j 1) になります。ここで、dp[j-1] は、部分文字列から削除する必要がある 0 の最小数 0...j-1 を表します。 s[ ] と (i-j 1) は、連続する 0 の部分文字列 s[j...i] を取得するために削除する必要がある 1 の総数です。そのようなインデックス j が見つからない場合は、連続する 0 の部分文字列に s[i] を含めることはできないため、dp[i] = dp[i-1] になります。

• 最後に、連続する 0 の部分文字列を取得するために、文字列 s 全体から削除する必要がある 0 の最小数は dp[n-1] で与えられます。ここで、n は文字列 s の長さです。

例 1

次のプログラムは、上で説明した方法を使用し、最初に標準入力から入力文字列を読み取り、次に 0 のすべての部分文字列を識別します。次に、最長の 0 部分文字列の長さと、各 0 部分文字列を連結して生成される文字列の長さを計算します。必要な削除の最小数を決定するために、最終的にすべての 0 部分文字列の合計から最も長い 0 部分文字列の長さを減算し、結果を標準出力に表示します。

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

方法 2: 反復法

このメソッドは、直接反復法を使用して、指定された文字列を 1 文字ずつ走査しながら、2 つの変数 count と max_count の値を更新します。このメソッドは、現在の文字が 0 か 1 に基づいて count 変数と max_count 変数の値を更新します。次に、max_count と最長の 0 部分文字列の長さの差が得られます。

例 2

の中国語訳は次のとおりです:

例 2

このコードは、バイナリ文字列から残りの文字列がゼロで区切られないようにすべてのゼロを削除するために必要な最小消去数を計算する C ソフトウェアです。 min_deletions 関数はバイナリ文字列を入力として受け取り、ループを使用して文字列内の各文字を反復処理します。ループは、ゼロに遭遇するたびに count 変数をインクリメントし、1 に遭遇するとカウント変数をゼロにリセットします。 count 変数の最大値は max_count に保存され、最後に文字列の長さが max_count から減算されて、必要な最小削除数が取得されます。結果はユーザーに表示されます。

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

0 のすべての部分文字列を決定すること、0 の各部分文字列を連結して生成される文字列の長さを計算すること、および最も長い 0 を含む部分文字列の長さを決定することは、指定された問題を解決するための 3 つのステップです。次に、すべての 0 部分文字列の合計から最大の 0 部分文字列の長さを減算して、必要な最小削除数を取得できます。

答えを得るために使用する方法はシンプルで効率的で、線形時間で実行されるため、大規模な入力に適しています。ただし、動的プログラミングなどのより高度な手法を適用することで、さらに強化することができます。

以上が文字列を 0 の文字列とその後に続く 1 の文字列で構成するための最小削除数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。