前缀和 / 后缀和，顺序遍历（两次 / 单次） 3 算法，求解《1422. 分割字符串的最大得分》和《2155. 分组得分最高的所有下标》
例题
1422. 分割字符串的最大得分
给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
示例 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
答案
前缀和 · 后缀和
var maxScore = function(s) {
const n = s.length, score0 = new Uint16Array(n), score1 = new Uint16Array(n)
for (let i = 0, j = 0; i < n - 1; i++) {
if (s[i] === '0') j++
score0[i] = j
}
for (let i = n, j = 0; i-- > 1;) {
if (s[i] === '1') j++
score1[i] = j
}
let r = 0
for (let i = 0; i < n - 1; i++) {
r = Math.max(r, score0[i] + score1[i + 1])
}
return r
};顺序遍历 · 两次遍历
var maxScore = function(s) {
const n = s.length
let score = 0
if (s[0] === '0') score++
for (let i = 1; i < n; i++) {
if (s[i] === '1') score++
}
let r= score
for (let i = 1; i < n - 1; i++) {
if (s[i] === '1') score--
else score++
r = Math.max(r, score)
}
return r
};function maxScore(s: string): number {
const n = s.length
let score = s[0] === '0' ? 1 : 0
for (let i = 1; i < n; i++) {
if (s[i] === '1') score++
}
let r = score
for (let i = 1; i < n - 1; i++) {
if (s[i] === '1') score--
else score++
if (score > r) r = score
}
return r
};class Solution {
function maxScore($s) {
$n = strlen($s);
$score = $s[0] === '0' ? 1 : 0;
for ($i = 1; $i < $n; $i++) {
if ($s[$i] === '1') $score++;
}
$r = $score;
for ($i = 1; $i < $n - 1; $i++) {
if ($s[$i] === '1') $score--;
else $score++;
if ($score > $r) $r = $score;
}
return $r;
}
}func maxScore(s string) int {
n, score := len(s), 0
if s[0] == '0' {
score = 1
} else {
score = 0
}
for i := 1; i < n; i++ {
if s[i] == '1' {
score++
}
}
r := score
for i := 1; i < n - 1; i++ {
if s[i] == '1' {
score--
} else {
score++
}
r = int(math.Max(float64(r), float64(score)))
}
return r
}class Solution {
public int maxScore(String s) {
int n = s.length(), score = s.charAt(0) == '0' ? 1 : 0;
for (int i = 1; i < n; i++) {
if (s.charAt(i) == '1') score++;
}
int r = score;
for (int i = 1; i < n - 1; i++) {
if (s.charAt(i) == '1') score--;
else score++;
r = Math.max(r, score);
}
return r;
}
}public class Solution {
public int MaxScore(string s) {
int n = s.Length, score = s[0] == '0' ? 1 : 0;
for (int i = 1; i < n; i++) {
if (s[i] == '1') score++;
}
int r = score;
for (int i = 1; i < n - 1; i++) {
if (s[i] == '1') score--;
else score++;
r = Math.Max(r, score);
}
return r;
}
}#define MAX(a, b) a > b ? a : b
int maxScore(char * s){
int n = strlen(s), score = s[0] == '0' ? 1 : 0;
for (int i = 1; i < n; i++) {
if (s[i] == '1') score++;
}
int r = score;
for (int i = 1; i < n - 1; i++) {
if (s[i] == '1') score--;
else score++;
r = MAX(r, score);
}
return r;
}class Solution {
public:
int maxScore(string s) {
int n = s.size(), score = s[0] == '1' ? 0 : 1;
for (int i = 1; i < n; i++) {
if (s[i] == '1') score++;
}
int r = score;
for (int i = 1; i < n - 1; i++) {
if (s[i] == '1') score--;
else score++;
r = max(r, score);
}
return r;
}
};class Solution:
def maxScore(self, s: str) -> int:
r = score = (s[0] == '0') + s[1:].count('1')
for i in range(1, len(s) - 1):
score += -1 if s[i] == '1' else 1
r = max(r, score)
return r顺序遍历 · 单次遍历
var maxScore = function(s) {
const n = s.length
let score0 = 0, score_score0All = 0
for (let i = 0; i < n - 1; i++) {
if (s[i] === '0') score0++
score_score0All = Math.max(score_score0All, (score0 << 1) + n - i - 1)
}
return score_score0All - score0 - (s[n - 1] === '0')
};function maxScore(s: string): number {
const n = s.length
let score0 = 0, score0_scoreAll = 0
for (let i = 0; i < n - 1; i++) {
if (s[i] === '0') score0++
score0_scoreAll = Math.max(score0_scoreAll, (score0 << 1) + n - i - 1)
}
return score0_scoreAll - score0 - (s[n - 1] === '0' ? 1 : 0)
};class Solution {
function maxScore($s) {
$n = strlen($s);
$score0 = 0;
$score0_scoreAll = 0;
for ($i = 0; $i < $n - 1; $i++) {
if ($s[$i] === '0') $score0++;
$score0_scoreAll = max($score0_scoreAll, ($score0 << 1) + $n - $i - 1);
}
return $score0_scoreAll - $score0 - ($s[$n - 1] === '0');
}
}func maxScore(s string) int {
n, score0, score0_scoreAll := len(s), 0, 0
for i := 0; i < n - 1; i++ {
if s[i] == '0' {
score0++
}
score0_scoreAll = int(math.Max(float64(score0_scoreAll), float64(score0 << 1 + n - i - 1)))
}
if s[n - 1] == '0' {
score0++
}
return score0_scoreAll - score0
}class Solution {
public int maxScore(String s) {
int n = s.length(), score0 = 0, score0_scoreAll = 0;
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == '0') score0++;
score0_scoreAll = Math.max(score0_scoreAll, (score0 << 1) + n - i - 1);
}
return score0_scoreAll - score0 - (s.charAt(n - 1) == '0' ? 1 : 0);
}
}public class Solution {
public int MaxScore(string s) {
int n = s.Length, score0 = 0, score0_scoreAll = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0') score0++;
score0_scoreAll = Math.Max(score0_scoreAll, (score0 << 1) + n - i - 1);
}
return score0_scoreAll - score0 - (s[n - 1] == '0' ? 1 : 0);
}
}#define MAX(a, b) a > b ? a : b
int maxScore(char * s){
int n = strlen(s), score0 = 0, score0_scoreAll = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0') score0++;
score0_scoreAll = MAX(score0_scoreAll, (score0 << 1) + n - i - 1);
}
return score0_scoreAll - score0 - (s[n - 1] == '0');
}class Solution {
public:
int maxScore(string s) {
int n = s.size(), score0 = 0, score0_scoreAll = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '0') score0++;
score0_scoreAll = max(score0_scoreAll, (score0 << 1) + n - i - 1);
}
return score0_scoreAll - score0 - (s[n - 1] == '0');
}
};class Solution:
def maxScore(self, s: str) -> int:
n, score0, score0_scoreAll = len(s), 0, 0
for i in range(0, n - 1):
if s[i] == '0': score0 += 1
score0_scoreAll = max(score0_scoreAll, (score0 << 1) + n - i - 1)
return score0_scoreAll - score0 - (s[n - 1] == '0')2155. 分组得分最高的所有下标
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [0,0,1,0]
输出：[2,4]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意，答案 [4,2] 也被视为正确答案。
示例 2：
输入：nums = [0,0,0]
输出：[3]
解释：按下标分组- 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
只有下标 3 可以得到最高的分组得分 3 。
示例 3：
输入：nums = [1,1]
输出：[0]
解释：按下标分组- 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。
- 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。
- 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。
只有下标 0 可以得到最高的分组得分 2 。
提示：
n == nums.length
1 <= n <= 105
nums[i] 为 0 或 1
答案
顺序遍历 · 单次遍历
var maxScoreIndices = function(nums) {
const n = nums.length, r = []
let score0 = 0, score0_scoreAll = 0
for (let i = 0; i <= n; i++) {
const t = (score0 << 1) + n - i
if (t > score0_scoreAll) {
score0_scoreAll = t
r.length = 0
r.push(i)
} else if (t === score0_scoreAll) r.push(i)
if (nums[i] === 0) score0++
}
return r
};function maxScoreIndices(nums: number[]): number[] {
const n = nums.length, r = []
let score0 = 0, score0_scoreAll = 0
for (let i = 0; i <= n; i++) {
const t = (score0 << 1) + n - i
if (t > score0_scoreAll) {
r.length = 0
r.push(i)
score0_scoreAll = t
} else if (t === score0_scoreAll) {
r.push(i)
}
if (nums[i] === 0) score0++
}
return r
};class Solution {
function maxScoreIndices($nums) {
$n = count($nums);
$r = [];
$score0 = $score0_scoreAll = 0;
for ($i = 0; $i <= $n; $i++) {
$t = ($score0 << 1) + $n - $i;
if ($t > $score0_scoreAll) {
$r = [$i];
$score0_scoreAll = $t;
} elseif ($t === $score0_scoreAll) {
$r []= $i;
}
if ($nums[$i] === 0) $score0++;
}
return $r;
}
}func maxScoreIndices(nums []int) []int {
n, r, score0, score0_scoreAll := len(nums), []int{}, 0, 0
for i := 0; i <= n; i++ {
t := score0 << 1 + n - i
if t > score0_scoreAll {
r = []int{i}
score0_scoreAll = t
} else if t == score0_scoreAll {
r = append(r, i)
}
if i < n && nums[i] == 0 {
score0++
}
}
return r
}class Solution {
public List<Integer> maxScoreIndices(int[] nums) {
int n = nums.length, score0 = 0, score0_scoreAll = 0;
List<Integer> r = new ArrayList<Integer>();
for (int i = 0; i <= n; i++) {
int t = (score0 << 1) + n - i;
if (t > score0_scoreAll) {
score0_scoreAll = t;
r.clear();
r.add(i);
} else if (t == score0_scoreAll) r.add(i);
if (i < n && nums[i] == 0) score0++;
}
return r;
}
}public class Solution {
public IList<int> MaxScoreIndices(int[] nums) {
int n = nums.Length, score0 = 0, score0_scoreAll = 0;
IList<int> r = new List<int>();
for (int i = 0; i <= n; i++) {
int t = (score0 << 1) + n - i;
if (t > score0_scoreAll) {
score0_scoreAll = t;
r.Clear();
r.Add(i);
} else if (t == score0_scoreAll) r.Add(i);
if (i < n && nums[i] == 0) score0++;
}
return r;
}
}int* maxScoreIndices(int* nums, int numsSize, int* returnSize){
int score0 = 0, score0_scoreAll = 0;
int* r = malloc(sizeof(int) * numsSize);
int pos = 0;
for (int i = 0; i <= numsSize; i++) {
int t = (score0 << 1) + numsSize - i;
if (t > score0_scoreAll) {
score0_scoreAll = t;
pos = 0;
r[0] = i;
} else if (t == score0_scoreAll) {
r[++pos] = i;
}
if (i < numsSize && nums[i] == 0) score0++;
}
returnSize[0] = pos + 1;
return r;
}class Solution {
public:
vector<int> maxScoreIndices(vector<int>& nums) {
int n = nums.size(), score0 = 0, score0_scoreAll = 0;
vector<int> r;
for (int i = 0; i <= n; i++) {
int t = (score0 << 1) + n - i;
if (t > score0_scoreAll) {
score0_scoreAll = t;
r.clear();
r.push_back(i);
} else if (t == score0_scoreAll) r.push_back(i);
if (i < n && nums[i] == 0) score0++;
}
return r;
}
};class Solution:
def maxScoreIndices(self, nums: List[int]) -> List[int]:
n, score0, score0_scoreAll, r = len(nums), 0, 0, []
for i in range(0, n + 1):
t = (score0 << 1) + n - i
if t > score0_scoreAll:
score0_scoreAll = t
r = [i]
elif t == score0_scoreAll: r.append(i)
if i < n and nums[i] == 0: score0 += 1
return r