网站建设策划目的及过程,疾控中心24小时咨询电话,安全员c证电子证书查询,阳朔网站建设公司划分字母区间 题解1 贪心1#xff08;方法略笨#xff0c;性能很差#xff09;题解2 贪心2#xff08;参考标答#xff09; 给你一个字符串
s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。 注意#xff0c;划分结果需要满足方法略笨性能很差题解2 贪心2参考标答 给你一个字符串
s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1 输入s ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。
示例 2 输入s eccbbbbdec 输出[10]
提示
1 s.length 500s 仅由小写英文字母组成
题解1 贪心1方法略笨性能很差 每次都在找当前字符所在的最大下标k可以保证该片段的最小长度nk-begin class Solution {
public:vectorint partitionLabels(string s) {int sl s.size();vectorint ret;int k s.rfind(s[0]);while(k 0 k sl){setchar 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 k1; i end; i)tmp.insert(s[i]);k end;end sl-1;}}ret.push_back(end);if(end sl-1)k s.rfind(s[end1]);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:vectorint partitionLabels(string s) {int last[26];int length s.size();for (int i 0; i length; i) {// 下标从小到大从左往右每个字符对应的位置都是最远位置// 反之最近位置last[s[i] - a] i;}vectorint 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;}
};
