763.划分字母区间

发表于： 分类于：
字数： 910 阅读：≈ 2分钟

🆎763.划分字母区间

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

示例：

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

思路

基本思想

同一个字母只能出现在一个片段中，所以需要记录字母结束位置，所以第一次遍历就记录当前字母的结束位置，第二次遍历就不断更新最远出现位置，一旦到了这个最远位置就形成一个分段

只要比最远位置大就更新最远位置

为什么到了这个最远位置就形成了一个分段，因为在到达这个最远位置的途中都没有超过这个最远位置的字母，说明这些字母都在最远位置的范围内，此时符合分段的条件，立马分段（因为要尽可能多的分段）

分段之后更新继续遍历，到达最远位置就可以分段

能成功到达最远位置就说明之前的字母都没有超过这个最远位置

执行流程

  1. 统计字母出现的最后位置，需要进行一次遍历，遇到一个字母就将更新他的最远距离

  2. 第二次遍历容器，更新最远距离，到达最远距离的下标立马分段

    既然能到达最远距离，之前的元素肯定没超过这个最远距离，因为最远距离实时更新

    image-20230607192903695

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[26] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int num = -1;
        int maxpos = 0;//默认最大位置是0，而不是pos[0]，这是从a开始
        //下标必须从0开始，防止丢掉第一个字符自成一段的情况
        for (int i = 0; i < S.size(); i++) {
            // 找到字符出现的最远边界，并且必须先更新当前字符
            if(hash[S[i] - 'a']>maxpos){
                maxpos=hash[S[i] - 'a'];
            }
            if (i == maxpos) {
                result.push_back(maxpos - num );
                num = i ;
            }
        }
        return result;
    }
};

总结

统计每一个字符出现的位置，之后遍历字符串s，判断每一个字符出现的最远位置，并实时更新这个最远位置，一旦到达最远位置，说明之前的字符都在最远位置的范围内，否则最远位置就会更新，此时可以进行一次分段，每次遍历到一个字符都需要更新最远距离

并且需要先更新最远距离再判断是否到达最远距离的位置，否则就是没考虑当前字符，结果会出错