侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心算法】划分字母区间

GabrielxD
2022-04-23 / 0 评论 / 0 点赞 / 131 阅读 / 431 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
## 题目

763. 划分字母区间


字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例 1:

输入:S = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。

提示:

  • S的长度在[1, 500]之间。
  • S只包含小写字母 'a''z'

解题

方法一:贪心算法

思路

只有小写字母就可以使用数组代替哈希表,记录每个字符最后一次出现的位置。 遍历字符串维护当前片段的开始下标 start 和结束下标 end,初始时 start = end = 0。 遍历到的每一个字符都拿到其最后一次的出现位置 lasts[strArr[i] - 'a'] ,则当前片段的结束下标一定不会小于该值,则 end = max(end, lasts[strArr[i] - 'a'])。 当访问到下标 end 时,当前片段访问结束,当前片段的下标范围是 $[start, end]$ ,长度为 $start - end + 1$,然后令 start = end + 1,继续寻找下一个片段。

代码

class Solution {
    public List<Integer> partitionLabels(String s) {
        char[] strArr = s.toCharArray();
        int len = strArr.length;
        int[] lasts = new int[26];
        for (int i = 0; i < len; i++) {
            lasts[strArr[i] - 'a'] = i;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0, start = 0, end = 0; i < len; i++) {
            end = Math.max(end, lasts[strArr[i] - 'a']);
            if (i == end) {
                ans.add(++end - start);
                start = end;
            }
        }

        return ans;
    }
}
0

评论区