力扣解题思路：763. 划分字母区间

763. 划分字母区间

思路：由题目字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。由此可以想到贪心算法，从第一个字符开始，往后找符合条件的最短字串，然后对后面的字串采用相同的分割方法-> 那么如何分割呢？从start遍历字符串，找到和起点相同的最后一个字母，查看此区间里的字母最后的end是否超出区间,超出则更新区间,直至找到最大的end则end-start + 1就是所求区间长度，然后更新start。-> 我们使用Map来存储每个字母的最后出现位置:

for(int i=0;i<S.length();i++){ map.put(S.charAt(i),i);//记录char c 和其最后出现位置的 map }

完整代码如下：

class Solution { public List<Integer> partitionLabels(String S) { if(S==null||S.length()==0) return null; List<Integer> list = new ArrayList<>(); Map<Character,Integer> map = new HashMap<>(); for(int i=0;i<S.length();i++){ map.put(S.charAt(i),i);//记录char c 和其最后出现位置的 map } int start = 0; int end = 0; for(int i=0;i<S.length();i++){ end = Math.max(end,map.get(S.charAt(i))); if(i==end){ list.add(end-start+1); start = i+1; } } return list; } }