分割字串後的最大分數

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中文網其他相關文章！