leetcode讲解--763. Partition Labels

题目A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.Example 1:Input: S = “ababcbacadefegdehijhklij"Output: [9,7,8]Explanation:The partition is “ababcbaca”, “defegde”, “hijhklij”.This is a partition so that each letter appears in at most one part.A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.Note:S will have length in range [1, 500].S will consist of lowercase letters (‘a’ to ‘z’) only.题目地址讲解这道题我居然一遍过，以前做题或多或少有些小错误。这道题我一上手就发现应该尽量阻止对数据的多次遍历，所以如果能遍历一遍得到一些有用的信息就好了。我用的解法是，建立一个map存储每个字母的首尾位置（当然实际操作中我用的是两个map分别存储字母第一次出现的位置和最后一次出现的位置）。然后如果这一段之间出现了一个字母，它的尾部位置比框住它的这个字母更大，就更新尾部位置，直到尾部位置无法再扩大为止。Java代码class Solution { public List<Integer> partitionLabels(String S) { List<Integer> result = new ArrayList<>(); char[] c = S.toCharArray(); Map<Character, Integer> mapStart = new HashMap<>(); Map<Character, Integer> mapEnd = new HashMap<>(); for(int i=0;i<c.length;i++){ if(mapStart.get(c[i])==null){ mapStart.put(c[i], i); mapEnd.put(c[i], i); }else{ mapEnd.put(c[i], i); } } int beginIndex=0; while(beginIndex<c.length){ int endIndex=mapEnd.get(c[beginIndex]); for(int i=beginIndex;i<endIndex;i++){ if(mapEnd.get(c[i])>endIndex){ endIndex = mapEnd.get(c[i]); } } result.add(endIndex-beginIndex+1); beginIndex = endIndex+1; } return result; }}