leecode 763 划分字母区间

题目：763. 划分字母区间

参考题解：划分字母区间-代码随想录

杜子腾，一遍揉，一遍考虑这道题目的思路。很快就想出来了。

核心思路：

1. 使用第一个字符，作为切割的切点start。
2. 从后向前，找到出现的第一个s[tmp_end]==s[start]。[start,tmp_end]必须在一个区间内。
3. 统计[start,tmp_end]中出现的字母放入set集合appr。从后向前查找，找到第一出现在appr的元素位置end。所以区间扩大到[start,end]。
4. 但是3中，会导致[tmp_end+1,end-1]引入新的不在appr中的元素。所以，我们需要修正end。修正方法和3类似，统计[tmp_end+1,end-1]中出现的新元素，再从后向前查找，修正end，扩大范围。

我第一次考虑的时候，只考虑到1-3步，所以用例通过了114/117。代码如下。

class Solution {
public:
    vector partitionLabels(string s) {
        // S的长度在[1, 500]之间。S只包含小写字母 'a' 到 'z' 。
        vector result;
        int start = 0, start_end, end; // 分别表示：切割区间的开始位置，和开始字符相同的最后一个字符位置，切割区间的最后一个位置

        for(int i=start; i=start; j--){ // 从后向前，找到和开始切割字符相同字符的最后位置
                if(s[j] == s[start]){
                    start_end = j;
                    break;
                }
            }

            set appr; // 记录[start,start_end]这个闭区间出现过的字符
            for(int j=start; j<=start_end; j++){
                appr.insert(s[j]);
            }

            for(int j=s.size()-1; j>=start_end; j--){ // 修正切割区间的终点，修正为区间中元素出现的最远位置
                if(appr.count(s[j])){
                    end = j;
                    break;
                }
            }

            result.push_back(end-start+1);
            start = end + 1;
            i = start;
        }

        return result;
    }
};

我需要修正上面的代码，以考虑到第4步。修正后的代码如下。可以成功通过。代码结构略微有些复杂。

#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector partitionLabels(string s) {
        // S的长度在[1, 500]之间。S只包含小写字母 'a' 到 'z' 。
        vector result;
        int start = 0, tmp_end, end; // 分别表示：切割区间的开始位置，和开始字符相同的最后一个字符位置，切割区间的最后一个位置

        for(int i=start; i=start; j--){ // 从后向前，找到和开始切割字符相同字符的最后位置
                if(s[j] == s[start]){
                    tmp_end = j;
                    break;
                }
            }

            set appr; // 记录[start,tmp_end]这个闭区间出现过的字符
            set appr_new;
            for(int j=start; j<=tmp_end; j++){
                appr.insert(s[j]);
            }

fixEnd:
            for(int j=s.size()-1; j>=tmp_end; j--){ // 修正切割区间的终点，修正为区间中元素出现的最远位置
                if(appr.count(s[j])){
                    end = j;
                    break;
                }
            }

            // 因为，[tmp_end+1,end-1]闭区间，可能出现不在appr中的新元素。所以需要重复修正，直到，[tmp_end+1,end-1]中的元素都出现在appr中
            for(int j=tmp_end+1; j<=end-1; j++){
                if(!appr.count(s[j])){
                    appr_new.insert(s[j]);
                    appr.insert(s[j]);
                }
            }

            if(appr_new.empty())
                ;
            else{
                tmp_end = end;
                appr_new.clear();
                goto fixEnd;
            }

            result.push_back(end-start+1);
            start = end + 1;
            i = start;
        }

        return result;
    }
};

int main(void){
    string s = "qiejxqfnqceocmy";
    Solution sol;
    vector result = sol.partitionLabels(s);
    for(int l : result)
        cout< 
方法二：使用附加空间记录最远距离-不断扩大右侧切割边界 
下面思路和代码，来自参考题解。
 
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。
 
 
class Solution {
public:
    vector partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};