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

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

難易度: 簡単

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

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

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

左部分文字列のゼロの数と、右の1の数を足したものです。部分文字列。

例 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」のみで構成されます。

ヒント:

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

解決策:

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

手順:

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

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

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

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

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

複雑：

• 時間計算量: 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

このソリューションは最適であり、制約内で問題を処理します。

連絡先リンク

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

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

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

• LinkedIn
• GitHub

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