当前位置：首页 > news >正文

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

news 2026/4/30 6:23:15

目录

一、题目描述

二、题目解答

2.1 思路

2.2 代码

三、总结

一、题目描述

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。

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

二、题目解答

2.1 思路

这道题的核心就在于同一个字母不能出现在两个片段中，而且切片的顺序不能乱，不能东切一片西切一片滴。所以我们可以计算出每个字母最后出现的顺序然后去切片。
思路：1. 定义一个长26的数组，遍历字符串，把字符串中的字母最后出现的位置记录下来
2. 定义起始量和结尾量还有最重要返回的列表
3. 遍历字符串，对当前字符更新 end = max(end，count[c])
若 i = end，就说明已经到达最大位置了，得分片了。这里要做两件事情：计算出当前切片长度并更新起始点位置
4. 返回结果

2.2 代码

class Solution { public List<Integer> partitionLabels(String s) { int[] count = new int[26]; for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); count[c - 'a'] = i; } List<Integer> result = new ArrayList<>(); int start = 0; int end = 0; for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); end = Math.max(end,count[c - 'a']); if(i == end){ int length = end - start + 1; result.add(length); start = end + 1; } } return result; } }