题目

leetcode:763

代码与解析

这道题挺难,我一开始想用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;
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:460536 人次
ICP备案号: 辽ICP备20003309号