バイナリ文字列を美しくするための最小限の変更数

2914。バイナリ文字列を美しくするための最小変更数

難易度: 中

トピック: 文字列

偶数の長さの 0 インデックス付き バイナリ文字列 s が与えられます。

次のような 1 つ以上の部分文字列に分割できる場合、文字列は 美しいです。

• 各部分文字列は偶数の長さを持ちます。
• 各部分文字列には、1 または 0 のみのみが含まれます。

s の任意の文字を 0 または 1 に変更できます。

文字列を美しくするために必要な変更の最小数を返します。

例 1:

• 入力: s = "1001"
• 出力: 2
• 説明: s[1] を 1 に、s[3] を 0 に変更して、文字列「1100」を取得します。
  • 文字列「1100」は「11|00」に分割できるため、美しいことがわかります。
  • 文字列を美しくするために必要な最小限の変更数は 2 であることが証明できます。

例 2:

• 入力: s = "10"
• 出力: 1
• 説明: s[1] を 1 に変更して、文字列「11」を取得します。
  • 文字列「11」は「11」に分割できるので美しいことがわかります。
  • 文字列を美しくするために必要な最小限の変更数は 1 であることが証明できます。

例 3:

• 入力: s = "0000"
• 出力: 0
• 説明: 文字列「0000」はすでに美しいため、変更を加える必要はありません。

制約:

• 2 5
• s の長さは偶数です。
• s[i] は '0' または '1' です。

ヒント:

1. 有効なパーティションの場合、各部分は偶数の同じ文字で構成されているため、各部分を正確に 2 の長さにさらに分割できます。
2. 最初のヒントに気づいたら、文字列全体をサイズ 2 の互いに素なブロックに分解し、それらのブロックを美しくするために必要な最小限の変更数を見つけることができます。

解決策:

バイナリ文字列 s 内のすべての文字のペアが「00」または「11」のいずれかであることを確認する必要があります。ペアがこれら 2 つのパターンのいずれにも当てはまらない場合、一致させるために文字の 1 つを変更する必要があります。

段階的な解決策のアプローチは次のとおりです:

1. 文字列をブロックに分割します: 美しい文字列は長さ 2 のブロックから形成できるため、文字列を 2 のステップで反復できます。

2. Count Changes: 2 文字のブロックごとに、多数の文字 (0 または 1) を決定する必要があります。ブロック内の少数文字を、多数文字と一致するように変更します。

3. 最小変更の計算: 各ブロックについて、両方の文字が異なる場合、1 つの変更が必要になります。それらが同じであれば、変更する必要はありません。

このソリューションを PHP で実装してみましょう: 2914。バイナリ文字列を美しくするための最小変更数

<?php
/**
 * @param String $s
 * @return Integer
 */
function minChanges($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
echo minChanges("1001"); // Output: 2
echo minChanges("10");   // Output: 1
echo minChanges("0000"); // Output: 0
?>

説明：

1. 関数定義: バイナリ文字列 s を受け取る関数 minChanges を定義します。

2. 初期化: 必要な変更の数を追跡するために、変数 $changes を初期化します。

3. 文字列を反復処理します: 文字列をループし、毎回 2 ずつ増分して 2 文字の各ブロックをチェックします:

   • $first は現在の位置の文字です。
   • $sec は次の位置の文字です。

4. 変更の確認: 現在のブロック内の文字が異なる場合、$changes カウンターを 1 つ増加します。

5. 戻り結果: 最後に、必要な変更の合計数を返します。

複雑：

• 時間計算量: O(n)、n は文字列の長さです。文字列を 1 回繰り返します。
• スペースの複雑さ: O(1)。一定量の追加スペースを使用しているためです。

このソリューションは、O(n) 時間計算量で動作します。ここで、n は文字列の長さであり、指定された制約に対して効率的です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がバイナリ文字列を美しくするための最小限の変更数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。