leecode 763 划分字母区间

怼烎@ 2022-09-15 06:02 89阅读 0赞

## 前言 ##

题目：[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<int> partitionLabels(string s) {
            // S的长度在[1, 500]之间。S只包含小写字母 'a' 到 'z' 。
            vector<int> result;
            int start = 0, start_end, end; // 分别表示：切割区间的开始位置，和开始字符相同的最后一个字符位置，切割区间的最后一个位置
    
            for(int i=start; i<s.size(); ){
    
                for(int j=s.size()-1; j>=start; j--){ // 从后向前，找到和开始切割字符相同字符的最后位置
                    if(s[j] == s[start]){
                        start_end = j;
                        break;
                    }
                }
    
                set<char> 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 <string>
    #include <vector>
    #include <set>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        vector<int> partitionLabels(string s) {
            // S的长度在[1, 500]之间。S只包含小写字母 'a' 到 'z' 。
            vector<int> result;
            int start = 0, tmp_end, end; // 分别表示：切割区间的开始位置，和开始字符相同的最后一个字符位置，切割区间的最后一个位置
    
            for(int i=start; i<s.size(); ){
    
                for(int j=s.size()-1; j>=start; j--){ // 从后向前，找到和开始切割字符相同字符的最后位置
                    if(s[j] == s[start]){
                        tmp_end = j;
                        break;
                    }
                }
    
                set<char> appr; // 记录[start,tmp_end]这个闭区间出现过的字符
                set<char> 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<int> result = sol.partitionLabels(s);
        for(int l : result)
            cout<<l<<" ";
    }

### 方法二：使用附加空间记录最远距离-不断扩大右侧切割边界 ###

下面思路和代码，来自参考题解。

*  统计每一个字符最后出现的位置
 *  从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

class Solution {
    public:
        vector<int> partitionLabels(string S) {
            int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
            for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
                hash[S[i] - 'a'] = i;
            }
            vector<int> 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;
        }
    };

[763.]: https://leetcode-cn.com/problems/partition-labels/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.md
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/393ced05bf6749e98b87ffb5f574e234.png