题目大意
#
描述：给定一个由若干 $0$ 和 $1$ 组成的字符串。将字符串分割成两个非空子字符串的得分为：左子字符串中 $0$ 的数量 + 右子字符串中 $1$ 的数量。
要求：计算并返回该字符串分割成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大得分。
说明：
- $2 \le s.length \le 500$。
- 字符串 $s$ 仅由字符 $0$ 和 $1$ 组成。
示例：
1
2
3
4
5
6
7
8
9
|
输入：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
|
1
2
3
|
输入：s = "00111"
输出：5
解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5
|
解题思路
#
思路 1：前缀和
#
- 遍历字符串 $s$，使用前缀和数组来记录每个前缀子字符串中 $1$ 的个数。
- 再次遍历字符串 $s$，枚举每个分割点，利用前缀和数组计算出当前分割出的左子字符串中 $1$ 的个数与右子字符串中 $0$ 的个数，并计算当前得分，然后更新最大得分。
- 返回最大得分作为答案。
思路 1：代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def maxScore(self, s: str) -> int:
size = len(s)
one_cnts = [0 for _ in range(size + 1)]
for i in range(1, size + 1):
if s[i - 1] == '1':
one_cnts[i] = one_cnts[i - 1] + 1
else:
one_cnts[i] = one_cnts[i - 1]
ans = 0
for i in range(1, size):
left_score = i - one_cnts[i]
right_score = one_cnts[size] - one_cnts[i]
ans = max(ans, left_score + right_score)
return ans
|
思路 1：复杂度分析
#
- 时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。
- 空间复杂度：$O(n)$。