【hot100-java】【划分字母区间】

R9-贪心算法篇

印象题：

我记得，先用字典记录每个字母出现的下标，取出首个字母的下标j,然后我们for循环遍历一次，如果该下标大于 j，就要变化新的首字母，如果相等就说明一个字符串完成，如果小于就继续遍历。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ret=new ArrayList<>();int [] dict=new int[26];for(int i=0;i<s.length();i++){dict[s.charAt(i)-'a']=i;}int num=0;int j=dict[s.charAt(0)-'a'];for (int i=0;i<s.length();i++){num++;if(dict[s.charAt(i)-'a']>j){j=dict[s.charAt(i)-'a'];}if(i==j){ret.add(num);num=0;}}return ret;}
}

ps: