Leetcode:763. Partition Labels

Posted on | Comments: | Views:
Greedy

763. Partition Labels

题目理解:

给出一个字符串S, 找到一个划分, 使得一个字母不会在两个部分出现

思路:

对于单个字母, 可以确定对这个字母所在的部分, 也就是它第一次出现的位置和最后一次出现的位置: [letter.first, letter.last]
但是这个区间有可能包含别的字母, 然后别的字母最后出现并不一定在这个区间, 所以还需要调整
可以这样想, 区间内的字母m, 与第一次出现的字母s, 视为同一部分, 那么这部分的划分就是 [s.start, m.last], 其中m可能是其中的任意字母, 只要保证最后出现的是同一类就行了
具体过程如下:

  • 1.遍历字符串, 记录每个字母最后出现的位置
  • 2.设定初始start为-1, last为0
  • 3.再遍历一遍字符串, 当last==当前遍历位置, 即找到一个划分, 添加last-start, 并将start设为当前遍历位置(last取得总是当前字母(t)最后出现的位置, 如果没有其他出现的更后, 那么最后会停在t最后出现的位置; 相反, 如果有一个字母比last出现得更后, 那么这个字母与前面为同一类, 找它的最后即可)

小结:

这道题是贴上贪心的标签, 实际不知道贪心体现在哪里..
时间复杂度为 O(n)

Submission Detail:

1

code:

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

        int flag = 0;
        int start = -1;
        for (int i = 0; i < S.size(); i++) {
            if (last[S[i]-'a'] > flag) {
                flag = last[S[i]-'a'];
            }
            if (flag == i) {
                v.push_back(flag-start);
                start = flag;
            }
        }
        return v;
    }
};