LeetCode763.划分字母区间

题目描述给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串 “ababcc” 能够被分为[“abab”, “cc”]但类似[“aba”, “bcc”] 或[“ab”, “ab”, “cc”] 的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。解题思路解题思路1先统计每个字符出现的频率从每个片段头开始遍历串每遍历一个字符就将该字符频率减一若当前字符频率为0则说明之后的串中不再出现该字符从片段头到当前字符若所有字符频率都为0则记录当前偏段数量更新片段头为当前字符下一位置否则重新找下一个字符频率为0的位置解题思路2先遍历一遍存储每个字符最后一次出现的位置然后找到该区间内的各字符最后一次位置的最大值当遍历位置走到最大值时便找到一个片段存储长度接着找下一个核心代码//思路1代码 vectorint Solution::partitionLabels(string s) { vectorint count(26, 0); //存放每个字符出现的频率 for (int i 0; i s.size(); i) { count[s[i] - a]; //统计频率 } int start 0; //记录每个片段的起始位置 vectorint result; for (int i 0; i s.size(); i) { //当前字符频率为0则检查该片段内所有字符频率是否都为0 //若是则输出片段长度若否则寻找下一个频率为0的字符 if ((--count[s[i] - a])0) { int j start; for (; j i; j) { if (count[s[j] - a] 0) {//存在频率不为0的字符 break; } } if (j i) { //当前片段符合题目要求 result.push_back(i - start 1); start i 1; } }//end if }//end for return result; } 思路2代码 vectorint Solution::partitionLabels(string s) { vectorint last(26, -1); // 记录每个字符最后出现的位置 for (int i 0; i s.size(); i) { last[s[i] - a] i; } vectorint result; int start 0, end 0; for (int i 0; i s.size(); i) { end max(end, last[s[i] - a]); // 当前片段必须到达当前字符的最后出现位置 if (i end) { // 找到一个片段 result.push_back(end - start 1); start end 1; }//end if }//end for return result; }完整可运行代码#includeiostream using namespace std; #includestring #includevector #includealgorithm class Solution { public: vectorint partitionLabels(string s); }; void Print(const vectorint result); int main() { string s; cin s; Solution solution; vectorint result solution.partitionLabels(s); Print(result); system(pause); return 0; } vectorint Solution::partitionLabels(string s) { vectorint count(26, 0); //存放每个字符出现的频率 for (int i 0; i s.size(); i) { count[s[i] - a]; //统计频率 } int start 0; //记录每个片段的起始位置 vectorint result; for (int i 0; i s.size(); i) { //当前字符频率为0则检查该片段内所有字符频率是否都为0 //若是则输出片段长度若否则寻找下一个频率为0的字符 if ((--count[s[i] - a])0) { int j start; for (; j i; j) { if (count[s[j] - a] 0) {//存在频率不为0的字符 break; } } if (j i) { //当前片段符合题目要求 result.push_back(i - start 1); start i 1; } }//end if }//end for return result; } void Print(const vectorint result) { for (int i 0; i result.size(); i) cout result[i] endl; } //思路2代码 //vectorint Solution::partitionLabels(string s) { // vectorint last(26, -1); // 记录每个字符最后出现的位置 // for (int i 0; i s.size(); i) { // last[s[i] - a] i; // } // vectorint result; // int start 0, end 0; // for (int i 0; i s.size(); i) {// 当前片段必须到达当前字符的最后出现位置 // end max(end, last[s[i] - a]); // if (i end) { // 找到一个片段 // result.push_back(end - start 1); // start end 1; // } // } // return result; //}补充知识使用std::fill(起始迭代器, 结束迭代器, 值)可一次性填充范围内的所有元素。int rfind(const string str, int pos npos) const;//查找str最后一次位置,从pos开始查找