C ++中的分区标签
假设我们给出了一个小写字母的字符串S。我们将这个字符串分成尽可能多的部分，以便每个字母最多显示一个部分，最后返回代表这些部分大小的整数列表。因此，如果字符串类似于“ababcbacadefegdehijhklij”，则输出为[9,7,8]，因为分区是“ababcbaca”，“defegde”，“hijhklij”。因此，这是一个分区，以便每个字母最多出现一个部分。像“ababcbacadefegde”，“hijhklij”之类的分区是不正确的，因为它将S分成更少的部分。
为了解决这个问题，我们将遵循以下步骤-
定义一个称为cnt的映射
对于范围在0到s之间的i，cnt[s[i]]：=i
j：=0，开始：=0且i：=0和n：=s的大小
定义一个数组ans
当我<n
j：=j和cnt[s[i]]的最大值
如果i=j，则将i–start+1插入ans并开始：=i+1
使我增加1
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
map <char, int> cnt;
for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
int j = 0, start = 0;
int i = 0;
int n = s.size();
vector <int> ans;
while(i < n){
j = max(j, cnt[s[i]]);
if( i == j){
ans.push_back(i-start+ 1);
start = i + 1;
}
i++;
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}输入值
"ababcbacadefegdehijhklij"
输出结果
[9,7,8]