题目
代码与解析
这道题挺难,我一开始想用map来记录字符位置,然后发现不大行
carl大佬的博客讲解
尤其这个图,很清晰,
这道题的关键在于 如果 字符最远出现位置下标和当前下标相等,则找到了位置
还有,要更新字符出现最远位置
s[i] - 'a'
: 单词在26字母中的索引
marks
:是一个26长度的数组
marks[s[i] - 'a']
: 记录每个字符出现的位置(最后位置)
![]()
func partitionLabels(s string) []int {
var res []int;
var marks [26]int;
size, left, right := len(s), 0, 0;
for i := 0; i < size; i++ {
// fmt.Println(marks[s[i] - 'a'])
// s[i] - 'a': 单词在26字母中的索引
// fmt.Println(s[i] - 'a')
// 记录26个字母中每个单词在s中出现的顺序,最后出现的次数
marks[s[i] - 'a'] = i;
}
// fmt.Println(marks)
for i := 0; i < size; i++ {
// 要更新right,他是划分区间的标准
right = max(right, marks[s[i] - 'a']);
if i == right {
res = append(res, right - left + 1);
left = i + 1;
}
}
return res;
}
func max(a, b int) int {
if a < b {
a = b;
}
return a;
}