繼續來寫貪心算法模塊

763. 劃分字母區間

給你一個字符串 s 。我們要把這個字符串劃分為儘可能多的片段，同一字母最多出現在一個片段中。例如，字符串 "ababcc" 能夠被分為 ["abab", "cc"]，但類似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的劃分是非法的。

注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是 s 。

返回一個表示每個字符串片段的長度的列表。

示例 1：

輸入：s = "ababcbacadefegdehijhklij" 輸出：[9,7,8]

解釋： 劃分結果為 "ababcbaca"、"defegde"、"hijhklij" 。

每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 這樣的劃分是錯誤的，因為劃分的片段數較少。

分析題目

這道題的解法和 上一題 跳躍遊戲Ⅱ 的解法十分類似

需要先明確字符串中每一個字母最後出現的位置，用哈希表來儲存

同一個字母只能出現在一個字符串中，所以要截取字符串必須找到這段字符串中所包含的所有字母的最遠邊界

例如：

要從s = "ababcbacadefegdehijhklij"中截取出ababcbaca，包含a,b,c三個字母，因為a在這段字符串中的最遠邊界處，就需要先明確a最後出現的位置，到達a的邊界才能截取字符串

代碼

class Solution {
    public List<Integer> partitionLabels(String s) {
        //用哈希表來儲存字母最後出現的位置
        Map<Character, Integer> map = new HashMap<>();

        //用一個列表來存儲截取到的字符串長度
        List<Integer> list = new ArrayList<>();

        //記錄起始索引位置，
        int start = 0;
        //記錄能截取的最遠邊界
        int fastest = 0;

        //儲存每個字母最後出現的位置
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);

        }
        //遍歷數組，更新截取部分的最遠邊界
        for (int i = 0; i < s.length(); i++) {
            fastest = Math.max(fastest,map.get(s.charAt(i)));
            //當到達最遠邊界時就可以對字符串進行截取
            if (i == fastest) {
                list.add(fastest-current+1);
          //截取完一次，就需要對起始索引進行更新，位置變為當前邊界的下一個位置
                current = fastest+1;
            }

        }


        return list;

    }
}

第一輪貪心算法小節刷完了！撒花！明天進入下一個新章節，棧！