Code & Fun

第30天,一个月了。

今天的题目是Partition Labels:

这道题的解法如下:

先遍历一次字符串统计字符出现的次数保存在c1上,然后在遍历一次字符串,这次遍历时同样进行统计字符出现次数保存在c2上,并维护一个变量cnum,这个变量cnum表示当前出现过但是未出现完全的字符的种类数。当出现cnum为 0 时,就表示完成了一次划分。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> partitionLabels(string S) {
vector<int> c1(26, 0);
for(int i = 0, size = S.size(); i < size; i++) {
c1[S[i] - 'a']++;
}

vector<int> c2(26, 0);
vector<int> res;
int temp = 1, cnum = 0;

for(int i = 0, size = S.size(); i < size; i++, temp++) {
int index = S[i] - 'a';
if (c2[index] == 0) {
cnum++;
}
if (++c2[index]== c1[index] && --cnum == 0) {
res.push_back(temp); temp = 0;
}
}
return res;
}

本文首发于Code & Fun