DX's Digital Garden

4._划分字母区间

2 min read

  • 2.17
    • 想到了字典记录最后位置，但是没搞懂怎么截取，使用 start 和 end 参数来计算子串长度
    • end 和3._跳跃游戏2一样，贪心更新
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] dict = new int[26];
        for(int i=0;i<s.length();i++){
            dict[s.charAt(i)-'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int start=0;
        int end = 0;
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            end = Math.max(end,dict[ch-'a']);
 
            if(i==end){
                res.add(end-start+1);
                start = i+1;
            }
        }
        return res;
    }
}

  • 2.3

    • 难点 1：用数组 dict 来存储每个字母最后的位置（for 中覆盖）
    • 难点 2：添加结果时用维护的 start 实现

  • 12.1

    1. 先进行上帝视角,用数组来存每个字母最远出现的位置
    2. 在后面进行划分时,思想和跳跃游戏2一样,更新最远的边界,如果到达边界,添加结果到res中,更新start
      • 边界end的更新逻辑为不断试探这一刀最少要砍在多远的地方

  • last[x] 就保存了每个字母 最后一次出现的索引位置。

  • end = Math.max(end,last[s.charAt(i)-‘a’]);更新最远的边界,比如

  • 2️⃣ 第二组

  • 下一段从 d（索引 9）开始，d 最后出现 14

  • 在 [9,14] 范围内，还出现 e(15)、f(11)、g(13)

  • 最大的末尾是 e(15) ​ ⇒ 第二段：[9–15]

last['a' - 'a'] = 8
last['b' - 'a'] = 5
last['c' - 'a'] = 7
...

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int[] last = new int[26];
        for(int i = 0;i<s.length();i++){
            last[s.charAt(i)-'a'] = i;
        }
        int start = 0, end = 0;
        for(int i=0;i<s.length();i++){
            end = Math.max(end,last[s.charAt(i)-'a']);
            if(i==end){
                res.add(end-start+1);
                start = i+1;
            }
        }
        return res;
    }
}

Graph View