大家好！我是曾续缘🤖
今天是《LeetCode 热题 100》系列
发车第 80 天
贪心算法第 4 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
提示：
1 <= s.length <= 500
s 仅由小写英文字母组成
难度：💖💖

解题方法

划分字母区间这个问题，要求我们将一个字符串尽可能多地划分为由相同字母组成的片段，同时保证连接起来的字符串仍然是原来的字符串。

记录每个字母的最后一个位置：
- 我们可以使用一个数组 last 来记录每个字母最后一次出现的索引位置。
- 遍历字符串 s 一次，对于每个字符，更新它对应的 last 数组值。
遍历字符串进行分割：
- 使用一个指针 start 来标记当前片段的开始位置。
- 使用一个变量 end 来标记当前片段的结束位置。
- 遍历字符串 s，对于每个字符，更新 end 为当前字符的 last 值和 end 中的较大值。
- 当 i == end 时，说明当前片段结束，我们将 end - start + 1 作为片段长度，并将其添加到答案列表中。
- 更新 start 为 end + 1，以开始搜索下一个片段。
返回答案：
- 遍历完成后，返回答案列表，其中包含了每个片段的长度。

Code

查看代码

java

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 创建一个数组，用于存储每个字母最后一次出现的位置
        int[] last = new int[26];
        int length = s.length(); // 获取字符串的长度
        // 遍历字符串，记录每个字母最后一次出现的位置
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> ans = new ArrayList<Integer>(); // 创建一个列表用于存储片段的长度
        int start = 0, end = 0; // 初始化开始和结束位置
        for (int i = 0; i < length; i++) {
            // 更新结束位置为当前字符的最后一个出现位置和end的较大值
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 如果当前索引i等于结束位置end，说明找到了一个片段的结束
            if (i == end) {
                // 将当前片段的长度添加到答案列表中
                ans.add(end - start + 1);
                // 更新开始位置为结束位置后一位，继续寻找下一个片段
                start = end + 1;
            }
        }
        return ans; // 返回答案列表
    }
}

解题方法 ​

Code ​

解题方法

Code