leetcode刷题笔记 763.划分字母区间（中等）

1.题目：

        字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

2.代码：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();

        //找到每个字符最后出现的位置
        for(int i = 0; i < length; ++i){
            last[s[i] - 'a'] = i;
        }
        int start =0, end = 0;
        vector<int> sss;    //存储划分的数据
        for(int i = 0; i < length; ++i){
            end = max(end, last[s[i] - 'a']);
            if(end == i){
                sss.push_back(end-start+1);
                start = end + 1;
            }
        }
        return sss;
    }
};

3.解题思路：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。

结合着上面的例子来看！！

同一个字母只能出现在同一个片段中，还要划分出尽量多的字符串数量，那么每个字母最后一次出现的位置，就有可能是划分字符串的位置，(例子中两次划分的位置是a和e最后出现的位置)在遍历字符串的过程中，通过比对已经遍历的字符最后出现的位置，位置最靠后的一定是截取端，（比如第一个字符串中，字母a的最后出现的位置是s[8],s[0]到s[8]之间包含的字母最后出现的位置都在s[8]之前）并且前一个字符串的结尾是下一个字符串的开头(s[8]是第一个字符串的结尾，s[9]是下一个字符串的开头)。

4.代码：

        @第一步：找到每个字符最后出现的位置，存储在一个数组中。

        @第二步：定义两个int类型变量start和end，初值均为0，start用于存储字符串的开头，end用于存储已经遍历到的字符串的最远结尾。每遍历一个字符就更新end的值，当end值恰好是当前遍历的位置时，到了截取字符串的位置，那么截取的长度就是end - start + 1，然后把(end + 1)赋值给start，重复操作即可。