69 划分字母区间

区间"/>

69 划分字母区间

划分字母区间

• • 题解1 贪心1（方法略笨，性能很差）
  • 题解2 贪心2（参考标答）

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

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

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

示例 2：
输入：s = "eccbbbbdec"
输出：[10]

提示：

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

题解1 贪心1（方法略笨，性能很差）

每次都在找当前字符所在的最大下标k，可以保证该片段的最小长度n>k-begin

class Solution {
public:vector<int> partitionLabels(string s) {int sl = s.size();vector<int> ret;int k = s.rfind(s[0]);while(k >= 0 && k < sl){set<char> tmp;int end = sl-1;for(int i = 0; i <= k; i++){tmp.insert(s[i]);}// 方向：从后往前// 原则：尽量多划，不在上一个段的也先选择划开while(end > k && !tmp.count(s[end])){end --;// 如果发现有重复字符 重新找k和end// 参考题解2 有更好的找最远位置的方法（last数组）if(end > k && tmp.count(s[end])){for(int i = k+1; i <= end; i++)tmp.insert(s[i]);k = end;end = sl-1;}}ret.push_back(end);if(end < sl-1)k = s.rfind(s[end+1]);else break;}// ret开始存的是下标，但题目要求返回长度（审题）for(int i = ret.size()-1; i > 0; i--)ret[i] = ret[i] - ret[i-1];ret[0] ++;return ret;}
};

题解2 贪心2（参考标答）

class Solution {
public:vector<int> partitionLabels(string s) {int last[26];int length = s.size();for (int i = 0; i < length; i++) {// 下标从小到大：从左往右：每个字符对应的位置都是最远位置// 反之，最近位置last[s[i] - 'a'] = i;}vector<int> partition;int start = 0, end = 0;for (int i = 0; i < length; i++) {// 在子串中去寻找最大的end值end = max(end, last[s[i] - 'a']);// 重点！！ 找到最大的end值后，i没有遍历到下一个子串前不会再有更大的end值if (i == end) {partition.push_back(end - start + 1);start = end + 1;}}return partition;}
};