1422。文字列分割後の最大スコア

難易度: 簡(jiǎn)単

トピック: 文字列、プレフィックス合計(jì)

0 と 1 の文字列 s を指定すると、文字列を 2 つの 空でない 部分文字列 (つまり、left 部分文字列と right 部分文字列).

文字列を分割した後のスコアは、

左部分文字列のゼロの數(shù)と、右の1の數(shù)を足したものです。部分文字列。

例 1:

• 入力: s = "011101"
• 出力: 5
• 説明: s を 2 つの空ではない部分文字列に分割する可能なすべての方法は次のとおりです。
  左 = "0"、右 = "11101"、スコア = 1 4 = 5
  左 = "01" および右 = "1101"、スコア = 1 3 = 4
  左 = "011" および右 = "101"、スコア = 1 2 = 3
  左 = "0111" および右 = "01"、スコア = 1 1 = 2
  左 = "01110" および右 = "1"、スコア = 2 1 = 3

例 2:

• 入力: s = "00111"
• 出力: 5
• 説明: 左 = "00"、右 = "111" の場(chǎng)合、最大スコア = 2 3 = 5 が得られます

例 3:

• 入力: s = "1111"
• 出力: 3

制約:

2 文字列 s は文字「0」と「1」のみで構(gòu)成されます。

ヒント:

1 のプレフィックス合計(jì) ('1') を事前計(jì)算します。
左から右にゼロ (「0」) の數(shù)を數(shù)えて反復(fù)し、事前に計(jì)算されたプレフィックスの合計(jì)を使用して 1 (「1」) を數(shù)えます。答えを更新します。

解決策:

文字列內(nèi)の 1 のプレフィックス合計(jì) ('1') を事前計(jì)算することで提供されるヒントを利用できます。解決策を詳しく説明します:

手順:

1. 1 のプレフィックス合計(jì): 文字列內(nèi)のインデックス i の各要素にインデックス i までの 1 の數(shù) (「1」) が含まれる配列を事前計(jì)算します。
2. 文字列を反復(fù)処理します: 各位置 i について、0 から i までの部分文字列を「左」部分文字列として扱い、i 1 から文字列の末尾までを「右」部分文字列として扱います。
   • 反復(fù)中に単純にカウントすることで、左側(cè)の部分文字列內(nèi)のゼロを數(shù)えます。
   • 接頭辭の合計(jì)を使用して、右側(cè)の部分文字列內(nèi)の 1 をカウントします (文字列內(nèi)の 1 の合計(jì)數(shù)から分割點(diǎn)の接頭辭の合計(jì)を減算します)。
3. スコアを計(jì)算する: 可能な分割ごとに、左側(cè)の部分文字列のゼロの數(shù)と右側(cè)の部分文字列の 1 の數(shù)を加算してスコアを計(jì)算します。
4. 最大スコアを返します。

このソリューションを PHP で実裝してみましょう:

1422。文字列分割後の最大スコア

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

// Test cases
$s1 = "011101";
$s2 = "00111";
$s3 = "1111";

echo "Input: $s1, Output: " . maxScore($s1) . PHP_EOL; // Output: 5
echo "Input: $s2, Output: " . maxScore($s2) . PHP_EOL; // Output: 5
echo "Input: $s3, Output: " . maxScore($s3) . PHP_EOL; // Output: 3
?>

説明：

1. プレフィックス合計(jì)の計(jì)算: 配列 $prefixOneCount 內(nèi)の 1 のプレフィックス合計(jì)を計(jì)算します。ここで、各インデックスは、その時(shí)點(diǎn)までの 1 の累積カウントを保持します。

2. 可能な分割の反復(fù): 各インデックス i (0 から n-2) の反復(fù)を開(kāi)始します。ここで、文字列は左側(cè)の部分 (0 から i) と右側(cè)の部分 ( i 1 から n-1 まで)。

   分割ごとに、左側(cè)の部分文字列 ($zeroCountLeft) のゼロを數(shù)えます。
   事前に計(jì)算された $prefixOneCount を使用して、正しい部分文字列に 1 がいくつあるかを計(jì)算します。

3. スコア計(jì)算: 各スプリットのスコアは、左側(cè)の部分の 0 と右側(cè)の部分の 1 の合計(jì)として計(jì)算されます。この反復(fù)中に発生した最大スコアを更新します。

4. 最終結(jié)果: この関數(shù)は、すべての分割中に見(jiàn)つかった最大スコアを返します。

複雑：

• 時(shí)間計(jì)算量: O(n)

  プレフィックス合計(jì)の事前計(jì)算と文字列の反復(fù)処理はどちらも
  • O(n) を要します。
  スコアを計(jì)算するために文字列を反復(fù)処理する場(chǎng)合も O(n) かかります。
  したがって、合計(jì)時(shí)間計(jì)算量は O(n) となり、指定された入力サイズ (n ≤ 500) に対して効率的です。

• 空間の複雑さ: O(n)

  プレフィックス合計(jì)配列には、
  • O(n) の追加スペースが必要です。

例：

echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3

このソリューションは最適であり、制約內(nèi)で問(wèn)題を処理します。

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で

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

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

• LinkedIn
• GitHub

以上が文字列分割後の最大スコアの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。