leetcode 763. Partition Labels 划分字母区间-耗时100%

Problem: 763. Partition Labels 划分字母区间

解题过程

耗时100%，首先统计每个字母的最小最大索引，然后合并所有字母的区间，可以合并的全部合并起来，不能合并的就放在那里，得到合并以后的区间，最后根据最小索引排序，输出每个区间的长度即可

Code

class Solution { public: pair<int, int> trg[26]; vector<int> partitionLabels(string s) { int ch; fill(trg, trg + 26, std::make_pair(1000, -1)); for(int i = 0; i < s.size(); i++) { ch = s[i] - 'a'; trg[ch].first = min(trg[ch].first, i); trg[ch].second = max(trg[ch].second, i); } int l, r; // for(int k = 0; k < 1; k++) { for(int i = 0; i < 26; i++) { if(trg[i].first==1000) continue; for(int j = 0; j < 26; j++) { if(i==j) continue; l = max(trg[i].first, trg[j].first); r = min(trg[i].second, trg[j].second); if( l <= r) { trg[i].first = min(trg[i].first, trg[j].first); trg[i].second = max(trg[i].second, trg[j].second); trg[j] = {1000, -1}; } } } // } sort(trg, trg + 26, [=](pair<int, int>&a, pair<int, int>&c) { return a.first < c.first; }); vector<int> tr; for(int i = 0; i < 26; i++) { if(trg[i].first==1000) return tr; tr.push_back(trg[i].second - trg[i].first + 1); } return tr; } };