划分字母区间
题意简述为
即最多能切多少段？使得同一字母都出现在一个片段，且片段最多。
思路
先统计整个字符串的map字典。
然后再次遍历字符串，当遍历字符串某一点时，当前字符串区间出现的字母个数就是整个字符串的字母个数（即当前字符串区间出现的字母，全部都出现在这里，区间外没有这个字母再次出现了），纪录当前区间是一段。
class Solution { public: vector<int> partitionLabels(string s) { map<char,int> my_map; //整个字符串字典 map<char,int> my_map_tmp;// 一段的字典 vector<int> result; int start = 0; //段开始标志 for(int i=0 ; i< s.size() ; i++) my_map[s[i]]++; // for(auto it:my_map) cout<<it.first<<' '<<it.second<<endl; for(int i=0 ; i<s.size() ;i++) { my_map_tmp[s[i]]++; //更新一段的字典 //检查当前的字典和全局字典，字母出现的次数 for(auto it = my_map_tmp.begin() ; it != my_map_tmp.end() ;it++) { //当前段中字母出现个数和全局不同（即还有字母没发现），跳出 if( it->second != my_map[it->first]) break; //当前段出现的字母，字母数量和全局数量都相同（即全发现） if(it == -- my_map_tmp.end() ) //遍历到最后一个字母都没跳出 { result.push_back(i-start+1); //记录段长度 start = i+1; //下一段开始点 my_map_tmp.clear();//清空段字典 } } } return result; } };
二刷
class Solution { public: vector<int> partitionLabels(string s) { map<char,int> my_map; vector<int> result; int left=0,right =0; for(int i=0 ; i<s.size() ;i++) { my_map[s[i]] = i; } // for(auto it:my_map) // { // cout<<it.first<<' '<<it.second<<endl; // } for(int i=0 ; i<s.size() ;i++) { right = max(right,my_map[s[i]]); if(right==i) { result.push_back(right-left+1); left = i+1; } } return result; } };
