分割字符串后的最大分数

1422。分割字符串后的最高分数

难度：简单

主题： 字符串、前缀和

给定一个由 0 和 1 组成的字符串 s，返回将字符串拆分为两个 非空子串（即 left 子串和 左子串后的最大分数） 🎜>右

子串）。

分割字符串后的分数是左子串中零的数量加上右中一

的数量子字符串。

示例1：

• 输入：
s = "011101"
• 输出：
5
• 解释：
  将 s 拆分为两个非空子字符串的所有可能方法是：
  左=“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')。
从左到右迭代计算零（“0”）的数量，然后使用预先计算的前缀和来计算“1”（“1”）。更新答案。

解决方案：

我们可以利用通过预先计算字符串中的前缀和 ('1') 提供的提示。以下是我们如何分解解决方案：

步骤：

1. 前缀和：预先计算一个数组，其中索引 i 处的每个元素都包含字符串中直至索引 i 的 1 个数 ('1')。
2. 迭代字符串：对于每个位置 i，将从 0 到 i 的子字符串视为“左”子字符串，将从 i 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 来计算右侧子字符串中有多少个。

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 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是分割字符串后的最大分数的详细内容。更多信息请关注PHP中文网其他相关文章！