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

難度：簡(jiǎn)單

主題： 字串、前綴和

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

子字串）。

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

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

範(fàn)例1：

• 輸入：
s = "011101"
• 輸出：
5
• 解釋?zhuān)?ul> 將 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

範(fàn)例2：

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

範(fàn)例 3：

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

約束：

2 字串 s 僅由字元「0」和「1」組成。

提示：

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

解：

我們可以利用透過(guò)預(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 到字串末尾的子字串視為「右”子字串。
   • 透過(guò)在迭代時(shí)簡(jiǎn)單地計(jì)算左子字串中的零來(lái)計(jì)算它們。
   • 使用前綴和來(lái)統(tǒng)計(jì)右子字串中的個(gè)數(shù)（透過(guò)從字串中的總個(gè)數(shù)中減去分割點(diǎn)處的前綴和）。
3. 計(jì)算分?jǐn)?shù)：對(duì)於每個(gè)可能的分割，計(jì)算分?jǐn)?shù)為左子字串中零的數(shù)量加上右子字串中1的數(shù)量。
4. 回傳最高分。

讓我們用 PHP 實(shí)作這個(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
?>

解釋?zhuān)?

1. 前綴和計(jì)算：我們計(jì)算數(shù)組 $prefixOneCount 中 1 的前綴和，其中每個(gè)索引保存截至該點(diǎn)的 1 的累積計(jì)數(shù)。

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

   • 對(duì)於每個(gè)分割，計(jì)算左子字串中的零 ($zeroCountLeft)。
   • 使用預(yù)先計(jì)算的 $prefixOneCount 來(lái)計(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ù)。

複雜：

• 時(shí)間複雜度：O(n)

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

• 空間複雜度：O(n)

  • 前綴和陣列需要O(n)額外空間。

例子：

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

這個(gè)解是最優(yōu)的，可以在限制範(fàn)圍內(nèi)處理問(wèn)題。

聯(lián)絡(luò)連結(jié)

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

如果您想要更多類(lèi)似的有用內(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)文章！