763.划分字母区间——之打开新世界

763.划分字母区间——之打开新世界
题目：
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

题目要求：

1. 尽可能多的片段
2. 相同字母合成到一个片段内

思路流程：
①只需要记录相同字母的位置即可->②记录相同字母位置最大范围即可->③合并重叠区间

输入：S = “ababcbaca defegde hijhklij”
a：[1,9]
b：[2,6]
c：[5,8]
d：[10,15]
e：[11,16]
h：[17,20]
i： [18,23]
j： [19,24]
此时已完成第②步，
【1,9】，【2,6】，【5,8】合并成【1,9】
【10,15】，【11,16】合并成【10,16】
【17，20】，【18，23】，【19,24】合并成【17,24】
此时就是所需要的答案了吗，可以发现此题经过处理之后与前面所做的合成区间几乎一模一样。所以称之为打开新世界。
代码：过不了，写了这么多总不能不发吧！！！生气！

class Solution {
public:
    static bool comparev(vector<int>& a, vector<int>& b){
        return a[1]<b[1];
    }
    vector<int> partitionLabels(string s) {
        vector<vector<int>> v;
        for(int i = 0; i < s.size();++i){  //遍历string
            if (v.size() == 0) {    //是否是入第一个元素
                vector<int> v0;
                v0.push_back(int(s[i]));  //入字母
                v0.push_back(0);            //入位置
            }
            else {      
                for(int j = 0; j < v.size();++j){       //遍历result，当前字母是否存在
                    if(v[j][0] == int(s[i])){
                        if(v[j].size() == 2){
                            v[j].push_back(i);
                        }
                        else{
                            if(v[j][2] < i) v[j][2] = i;
                        }
                    }
                    else{
                        vector<int> v0;
                        v0.push_back(int(s[i]));  //入字母
                        v0.push_back(i);            //入位置
                    }
                }
            }
        }
        sort(v.begin(),v.end(),comparev);
        vector<int> v1;
        int begin = v[0][1];
        int end = v[0][2];
        for(int i = 1; i < v.size();i++){
            if(v[i][1] < end){
                if(v[i][2] > end){
                    end = v[i][2];
                }
            }
            else{
              v1.push_back(end-begin+1);
               begin = v[i][1];
               end = v[i][2];
            }
        }
        v1.push_back(end-begin+1);
        return v1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

代码实现比较复杂还没实现，后来看了力扣题解发现更简单方法
解析：
在脑海中想象出由一个个动态字符构成的字符串，将其划分为三个片段，第一个片段的起始值是第一个值，末尾值是这个片段中间的某个值的end，第二个片段的起始值是上个片段的end+1对应的那个值，end是这个片段中间的某个值的end，第三个片段类似。
代码：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int far[27]={0};
        for (int i = 0; i < s.length();++i){        //记录字符串中字母出现的最远下标
            far[s[i]-'a'] = i;
        }
        //字母区间的合并同时记录区间长度
        int start = 0;
        int end = 0;
        vector<int> v;
        for(int i = 0 ; i < s.size(); ++i){//筛选区间
            end = max(end,far[s[i]-'a']);
            if( i == end){
                v.push_back(end-start+1);
                start = i+1;
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21