算法刷题记录——LeetCode篇(8.7) [第761~770题](持续更新)

更新时间：2025-03-30

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]

划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

---

方法一：贪心算法

1. 记录每个字符的最后出现位置：首先遍历字符串，记录每个字符最后一次出现的索引，为后续分割提供依据。
2. 维护当前片段的起止位置：再次遍历字符串，动态维护当前片段的结束位置，确保所有已遍历字符的最后出现位置均包含在当前片段中。当遍历到当前片段的结束位置时，立即分割，确保每个字符仅属于一个片段，并开始下一个片段的处理。

代码实现(Java)：

class Solution {public List<Integer> partitionLabels(String s) {// 记录每个字符的最后出现位置int[] lastOccurrence = new int[26];int length = s.length();for (int i = 0; i < length; i++) {char c = s.charAt(i);lastOccurrence[c - 'a'] = i;}List<Integer> partitions = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < length; i++) {char currentChar = s.charAt(i);// 扩展当前片段的结束位置end = Math.max(end, lastOccurrence[currentChar - 'a']);// 当遍历到当前片段的结束位置时，分割并记录if (i == end) {partitions.add(end - start + 1);start = end + 1; // 下一个片段的起始位置}}return partitions;}
}

动态规划法复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串的长度。两次遍历字符串的时间复杂度均为 O(n)。
• 空间复杂度：O(1)，使用固定大小的数组存储字符的最后出现位置。

---

方法二：合并区间（理论补充）

1. 生成字符区间：记录每个字符的首次和最后一次出现的位置，生成区间集合。
2. 合并重叠区间：将所有重叠的区间合并，合并后的每个区间对应一个最终的分段。

合并区间法复杂度分析：

• 时间复杂度：O(n + m log m)，其中 m 是不同字符的数量（最多26个），实际性能不如贪心算法。
• 空间复杂度：O(m)，需要存储所有字符的区间。

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。