763.划分字母区间 (Medium)
# 题目描述
# 样例
Input:S = "ababcbacadefegdehijhklij"
Output:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。
1
2
3
4
5
6
2
3
4
5
6
# 题解
贪心算法,使用一个变量 end 记录每段字符的某位,每次更新字符的end 位置。
# 代码示例
Python 示例
class Solution:
def partitionLabels(self, S: str) -> List[int]:
last = {}
for idx, s in enumerate(S):
last[s] = idx
start, end = 0, 0
label = []
for idx, s in enumerate(S):
end = max(end, last[s])
if idx == end: # 走到end,划分字母
label.append(end - start + 1)
start = idx + 1 # 开新的区间
return label
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
Go 示例
func max(a, b int) int {
if a > b { return a}
return b
}
func partitionLabels(S string) []int {
n := len(S)
last := make(map[rune]int, n)
for idx, s := range S { // 记录字符的最后的位置
last[s] = idx
}
start, end := 0, 0
ans := make([]int, 0)
for idx, s := range S {
end = max(end, last[s]) //不停更新每个分段的end位置
if idx == end { // 走到end, 开始划分字母
ans = append(ans, end - start + 1) // 计算长度,加入结果集中
start = idx + 1
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
编辑 (opens new window)
上次更新: 2021/06/09, 11:50:03