【玩转贪心算法专题】763. 划分字母区间【中等】
1、力扣链接
https://leetcode.cn/problems/partition-labels/description/
2、题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = “eccbbbbdec”
输出：[10]
提示：
1 <= s.length <= 500
s 仅由小写英文字母组成
3、题目分析
对于贪心算法的题目，可从 寻求局部最优解入手，以局部最优解，得到全局最优解
本题思路：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
4、代码实现
1、Java
class Solution {public List<Integer> partitionLabels(String s) {//记录最后结果List<Integer> list = new LinkedList<>();//记录每个字母出现的最远位置int[] edge = new int[26];char[] chars = s.toCharArray();for(int i=0;i < chars.length; i++){//'a'-'a' edge[0] = 8;edge[chars[i] - 'a'] = i;}//右边界int idx = 0;//左边界int last = -1;for(int i=0; i< chars.length;i++){//本次遍历到的idx 最远距离idx = Math.max(idx,edge[chars[i] - 'a']);//如果相等if(i == idx){//记录一个片段list.add(i-last);last = i;}}return list;}
}
2、C++
class Solution {
public:static bool cmp(vector<int> &a, vector<int> &b) {return a[0] < b[0];}// 记录每个字母出现的区间vector<vector<int>> countLabels(string s) {vector<vector<int>> hash(26, vector<int>(2, INT_MIN));vector<vector<int>> hash_filter;for (int i = 0; i < s.size(); ++i) {if (hash[s[i] - 'a'][0] == INT_MIN) {hash[s[i] - 'a'][0] = i;}hash[s[i] - 'a'][1] = i;}// 去除字符串中未出现的字母所占用区间for (int i = 0; i < hash.size(); ++i) {if (hash[i][0] != INT_MIN) {hash_filter.push_back(hash[i]);}}return hash_filter;}vector<int> partitionLabels(string s) {vector<int> res;// 这一步得到的 hash 即为无重叠区间题意中的输入样例格式：区间列表// 只不过现在我们要求的是区间分割点vector<vector<int>> hash = countLabels(s);// 按照左边界从小到大排序sort(hash.begin(), hash.end(), cmp);// 记录最大右边界int rightBoard = hash[0][1];int leftBoard = 0;for (int i = 1; i < hash.size(); ++i) {// 由于字符串一定能分割，因此,// 一旦下一区间左边界大于当前右边界，即可认为出现分割点if (hash[i][0] > rightBoard) {res.push_back(rightBoard - leftBoard + 1);leftBoard = hash[i][0];}rightBoard = max(rightBoard, hash[i][1]);}// 最右端res.push_back(rightBoard - leftBoard + 1);return res;}
};
3、python
class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {} # 存储每个字符最后出现的位置for i, ch in enumerate(s):last_occurrence[ch] = iresult = []start = 0end = 0for i, ch in enumerate(s):end = max(end, last_occurrence[ch]) # 找到当前字符出现的最远位置if i == end: # 如果当前位置是最远位置，表示可以分割出一个区间result.append(end - start + 1)start = i + 1return result4、go
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++ {marks[s[i] - 'a'] = i;}for i := 0; i < size; i++ {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;
}
