【重点】【贪心】763.划分字母区间

题目

法1：贪心

思路和跳跃游戏II一模一样，只是细节稍有出入，对比记忆！！！

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        char_dict = dict()
        for i in range(len(s)):
            char_dict[s[i: i+1]] = i
        cur_max = -1
        cur_start = 0
        res = list()
        for i in range(len(s)):
            tmp_char = s[i: i+1]
            cur_max = max(cur_max, char_dict[tmp_char])
            if i == cur_max:
                res.append(cur_max - cur_start + 1)
                cur_start = i + 1
                cur_max = -1
        
        return res

Java

// 使用map记录索引
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> charToLastIndexMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            charToLastIndexMap.put(c, s.lastIndexOf(c));
        }
        int start = 0, maxPos = 0;
        for (int i = 0; i < s.length(); ++i) {
            maxPos = Math.max(maxPos, charToLastIndexMap.get(s.charAt(i)));
            if (i == maxPos) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}

// 使用数组保存索引
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int[] lastIndexArray = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            lastIndexArray[s.charAt(i) - 'a'] = i;
        }
        int start = 0, maxPos = 0;
        for (int i = 0; i < s.length(); ++i) {
            maxPos = Math.max(maxPos, lastIndexArray[s.charAt(i) - 'a']);
            if (i == maxPos) {
                res.add(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}