2914。バイナリ文字列を美しくするための最小変更數(shù)

難易度: 中

トピック: 文字列

偶數(shù)の長(zhǎng)さの 0 インデックス付き バイナリ文字列 s が與えられます。

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

• 各部分文字列は偶數(shù)の長(zhǎng)さを持ちます。
• 各部分文字列には、1 または 0 のみのみが含まれます。

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

文字列を美しくするために必要な変更の最小數(shù)を返します。

例 1:

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

例 2:

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

例 3:

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

制約:

• 2 5
• s の長(zhǎng)さは偶數(shù)です。
• s[i] は '0' または '1' です。

ヒント:

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

解決策:

バイナリ文字列 s 內(nèi)のすべての文字のペアが「00」または「11」のいずれかであることを確認(rèn)する必要があります。ペアがこれら 2 つのパターンのいずれにも當(dāng)てはまらない場(chǎng)合、一致させるために文字の 1 つを変更する必要があります。

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

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

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

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

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

<?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. 関數(shù)定義: バイナリ文字列 s を受け取る関數(shù) minChanges を定義します。

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

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

   • $first は現(xiàn)在の位置の文字です。
   • $sec は次の位置の文字です。

4. 変更の確認(rèn): 現(xiàn)在のブロック內(nèi)の文字が異なる場(chǎng)合、$changes カウンターを 1 つ増加します。

5. 戻り結(jié)果: 最後に、必要な変更の合計(jì)數(shù)を返します。

複雑：

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

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

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

以上がバイナリ文字列を美しくするための最小限の変更數(shù)の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。