1422。分割字符串后的最高分?jǐn)?shù)

難度：簡(jiǎn)單

主題： 字符串、前綴和

給定一個(gè)由 0 和 1 組成的字符串 s，返回將字符串拆分為兩個(gè) 非空子串（即 left 子串和 左子串后的最大分?jǐn)?shù)） ??>右

子串）。

分割字符串后的分?jǐn)?shù)是左子串中零的數(shù)量加上右中一

的數(shù)量子字符串。

示例1：

• 輸入：
s = "011101"
• 輸出：
5
• 解釋：
  將 s 拆分為兩個(gè)非空子字符串的所有可能方法是：
  左=“0”，右=“11101”，分?jǐn)?shù)= 1 4 = 5
  左=“01”，右=“1101”，分?jǐn)?shù)= 1 3 = 4
  左=“011”，右=“101”，分?jǐn)?shù)= 1 2 = 3
  左=“0111”，右=“01”，分?jǐn)?shù)= 1 1 = 2
  左=“01110”，右=“1”，分?jǐn)?shù)= 2 1 = 3

示例2：

• 輸入：
s = "00111"
• 輸出：
5
• 解釋：
當(dāng)左 = "00" 右 = "111" 時(shí)，我們得到最大分?jǐn)?shù) = 2 3 = 5

示例 3：

• 輸入：
s = "1111"
• 輸出：
3

約束：

2 字符串 s 僅由字符“0”和“1”組成。

提示：

預(yù)先計(jì)算前綴和 ('1')。
從左到右迭代計(jì)算零（“0”）的數(shù)量，然后使用預(yù)先計(jì)算的前綴和來計(jì)算“1”（“1”）。更新答案。

解決方案：

我們可以利用通過預(yù)先計(jì)算字符串中的前綴和 ('1') 提供的提示。以下是我們?nèi)绾畏纸饨鉀Q方案：

步驟：

1. 前綴和：預(yù)先計(jì)算一個(gè)數(shù)組，其中索引 i 處的每個(gè)元素都包含字符串中直至索引 i 的 1 個(gè)數(shù) ('1')。
2. 迭代字符串：對(duì)于每個(gè)位置 i，將從 0 到 i 的子字符串視為“左”子字符串，將從 i 1 到字符串末尾的子字符串視為“右”子字符串。
   • 通過在迭代時(shí)簡(jiǎn)單地計(jì)算左子字符串中的零來計(jì)算它們。
   • 使用前綴和來統(tǒng)計(jì)右子串中的個(gè)數(shù)（通過從字符串中的總個(gè)數(shù)中減去分割點(diǎn)處的前綴和）。
3. 計(jì)算分?jǐn)?shù)：對(duì)于每個(gè)可能的分割，計(jì)算分?jǐn)?shù)為左子字符串中零的數(shù)量加上右子字符串中1的數(shù)量。
4. 返回最高分。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：1422。分割字符串后的最高分?jǐn)?shù)

<?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ì)算數(shù)組 $prefixOneCount 中 1 的前綴和，其中每個(gè)索引保存截至該點(diǎn)的 1 的累積計(jì)數(shù)。

2. 迭代可能的拆分：我們開始迭代每個(gè)索引 i（從 0 到 n-2），其中字符串被拆分為左部分（從 0 到 i）和右部分（從 i 1 到 n-1)。

   • 對(duì)于每個(gè)分割，計(jì)算左子字符串中的零 ($zeroCountLeft)。
   • 使用預(yù)先計(jì)算的 $prefixOneCount 來計(jì)算右側(cè)子字符串中有多少個(gè)。

3. 分?jǐn)?shù)計(jì)算：每個(gè)分割的分?jǐn)?shù)計(jì)算為左側(cè)部分的 0 和右側(cè)部分的 1 的總和。我們更新本次迭代中遇到的最大分?jǐn)?shù)。

4. 最終結(jié)果：函數(shù)返回所有分割期間找到的最大分?jǐn)?shù)。

復(fù)雜：

• 時(shí)間復(fù)雜度：O(n)

  • 預(yù)計(jì)算前綴和并迭代字符串都需要 O(n).
  • 迭代字符串來計(jì)算分?jǐn)?shù)也需要 O(n)。
  • 因此，總時(shí)間復(fù)雜度為 O(n)，這對(duì)于給定的輸入大小 (n ≤ 500) 是有效的。

• 空間復(fù)雜度：O(n)

  • 前綴和數(shù)組需要O(n)額外空間。

例子：

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

這個(gè)解決方案是最優(yōu)的，可以在限制范圍內(nèi)處理問題。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是分割字符串后的最大分?jǐn)?shù)的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！