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

難易度: 簡単

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

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" の場合、最大スコア = 2 3 = 5 が得られます

例 3:

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

制約:

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

ヒント:

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

解決策:

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

手順:

1. 1 のプレフィックス合計: 文字列內(nèi)のインデックス i の各要素にインデックス i までの 1 の數(shù) (「1」) が含まれる配列を事前計算します。
2. 文字列を反復処理します: 各位置 i について、0 から i までの部分文字列を「左」部分文字列として扱い、i 1 から文字列の末尾までを「右」部分文字列として扱います。
   • 反復中に単純にカウントすることで、左側(cè)の部分文字列內(nèi)のゼロを數(shù)えます。
   • 接頭辭の合計を使用して、右側(cè)の部分文字列內(nèi)の 1 をカウントします (文字列內(nèi)の 1 の合計數(shù)から分割點の接頭辭の合計を減算します)。
3. スコアを計算する: 可能な分割ごとに、左側(cè)の部分文字列のゼロの數(shù)と右側(cè)の部分文字列の 1 の數(shù)を加算してスコアを計算します。
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. プレフィックス合計の計算: 配列 $prefixOneCount 內(nèi)の 1 のプレフィックス合計を計算します。ここで、各インデックスは、その時點までの 1 の累積カウントを保持します。

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

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

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

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

複雑：

• 時間計算量: O(n)

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

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

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

例：

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

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

連絡(luò)先リンク

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

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

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

• LinkedIn
• GitHub

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