763. 划分字母区间(leetcode)

LXL's Blog / 2024-08-29 / 原文

https://leetcode.cn/problems/partition-labels/description/

听说这题是字节广告一面的题
有两种做法,但是思路大致相同,主要思路是先求出所有字符的出现的最远距离,然后不断往后遍历,更新当前片段的最远距离

若是第一种做法,就是放在另一个循环中,不断更新最远距离,且维护这个end,维护完毕后end就是当前片段的结尾
第二种做法也是官方做法,即不断更新片段最远距离,且往后遍历,直到遍历的位置是最远距离时
意味着这个最远距离已经更新完毕了,被正常遍历给追上了,即这个位置是当前片段的最远距离

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 思路是不断遍历,遍历到没遍历过的字符就更新当前片段的最远距离
        List<Integer> res = new ArrayList<>();
        // 计算每个字符出现的最远位置
        Map<Character,Integer> pMap = new HashMap<>();
        for(int i=0;i<s.length();i++)
            pMap.put(s.charAt(i),i);
        int i=0;
        while(i<s.length())
        {
            // 获取此时的片段end
            int end=pMap.get(s.charAt(i));
            
            for(int j=i;j<end;j++)
            {
                // 更新end
                end=Math.max(end,pMap.get(s.charAt(j)));
            }
            // 更新end完毕,此时end就是当前片段的结尾
            // 加入答案
            res.add(end-i+1);
            // 更新新的片段起点
            i=end+1;
        }
        return res;

    }
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 思路是不断遍历,遍历到没遍历过的字符就更新当前片段的最远距离
        // 贪心的地方在于当前位置和最远距离位置相同就是片段分割点
        List<Integer> res = new ArrayList<>();
        // 计算每个字符出现的最远位置
        Map<Character,Integer> pMap = new HashMap<>();
        for(int i=0;i<s.length();i++)
            pMap.put(s.charAt(i),i);
        int idx = 0;
        int last = -1;
        for (int i = 0; i < s.length(); i++) {
            // 更新当前片段的最远距离
            idx = Math.max(idx,pMap.get(s.charAt(i)));
            if (i == idx) {
                // 当前位置是当前片段的最远距离,这里是贪心的地方,也是难点
                // 且由于取的都是尽可能短的片段,因此得到的数量是最多的,这里也是贪心
                res.add(i - last);
                last = i;
            }
        }
        return res;

    }
}