バイナリ文字列を昇順に並べ替えるために削除する必要がある文字の最小数

コンピューター サイエンスでは、文字列の操作は重要なトピックであり、スプライシング、部分文字列、反転などの操作が含まれます。文字列操作に関連する一般的な問題は、バイナリ文字列からすべてのゼロを削除することです。この記事では、この問題を解決するために、最小数の非隣接ペア反転を使用するアルゴリズムについて説明します。

＃＃＃問題文＃＃＃

バイナリ文字列が与えられた場合、最小数の非隣接ペア反転を使用して文字列内のすべての 0 を削除する必要があります。反転は、2 つの隣接する文字を選択し、それらを入れ替えることとして定義されます。言い換えれば、文字列内のすべての 0 を文字列の最後に持ってくるために必要な反転の最小数を見つける必要があります。

＃＃＃方法＃＃＃

貪欲アルゴリズムを使用して、この問題を解決できます。文字列の左側から開始して、0 を反転した最後のインデックスを最後まで追跡できます。遭遇した 0 ごとに、その位置を最後に反転された 0 と交換し、文字列の末尾に移動します。 1 が見つかった場合は、単純に次のインデックスに移動します。

アルゴリズムを詳しく見てみましょう -

2 つの変数「lastFlipped」と「flipCount」をそれぞれ -1 と 0 に初期化します。

• バイナリ文字列を左から右にトラバースします。

• 現在の文字が「0」の場合、それをインデックス「lastFlipped 1」の文字と交換し、「lastFlipped」変数をインクリメントします。

• スワップ操作ごとに「flipCount」変数を増やします。

• トラバーサルが完了すると、すべての 0 が文字列の末尾になり、「flipCount」にはすべての 0 を削除するために必要な最小の反転数が含まれます。

• ＃＃＃例＃＃＃

  これは、上記のアルゴリズムを実装するために使用される C コードです -

  リーリー ＃＃＃出力＃＃＃ リーリー
テストケースの説明

バイナリ文字列「100101000」を例として取り上げます。最小数の非隣接ペア反転を使用して、文字列からすべての 0 を削除する必要があります。

最初、「lastFlipped」と「flipCount」はそれぞれ -1 と 0 に設定されます。

• 文字列を左から右にトラバースし始めます。

• インデックス 1 で「0」が見つかりました。これをインデックス「lastFlipped 1」(つまりインデックス 0) の文字と交換し、「lastFlipped」を 0 にインクリメントします。文字列は「010101000」になります。 「flipCount」が 1 に増加します。

• インデックス 4 で、別の「0」が出現します。これをインデックス「lastFlipped 1」(つまりインデックス 1) の文字と交換し、「lastFlipped」を 1 にインクリメントします。文字列は「011010000」になります。 「flipCount」が 2 に増加します。

• インデックス 5 で、「1」が見つかります。次のインデックス

に移動するだけです
• ＃＃＃結論は＃＃＃

  この記事では、最小数の非隣接ペア反転を使用してバイナリ文字列からすべての 0 を削除するアルゴリズムについて説明します。このアルゴリズムで使用されるアプローチは貪欲であるため、効率的で実装が容易になります。アルゴリズムを実装するための C コードとサンプル テスト ケースも提供します。

この問題は動的プログラミングを使用して解決することもできますが、貪欲アルゴリズムの方がよりシンプルで高速な解決策を提供します。このアルゴリズムの時間計算量は O(n) です。ここで、n はバイナリ文字列の長さです。

• つまり、最小非隣接ペア反転アルゴリズムは文字列操作で便利なツールであり、さまざまな状況に適用できます。

以上がバイナリ文字列を昇順に並べ替えるために削除する必要がある文字の最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。