重庆高铁建设网站,秦皇岛做网站外包,莱芜二中网站,小米商城网站建设思路#xff1a;贪心
其实这个题目并不难#xff0c;只需要分析出来每一个字母最后出现的坐标就行。
我们根据字母最后出现的坐标数来判断最后划分的字符串。
比如说#xff0c;字符串前面有abc#xff0c;这三个字母最后出现的地方就是这个位置#xff0c;那么我们直接…思路贪心
其实这个题目并不难只需要分析出来每一个字母最后出现的坐标就行。
我们根据字母最后出现的坐标数来判断最后划分的字符串。
比如说字符串前面有abc这三个字母最后出现的地方就是这个位置那么我们直接划分就行但是如果说其中一个字母的最后坐标在远处我们就需要以这个最远的坐标为主划分字符串。
所以在我们遍历的时候需要每遍历一次字符串就需要更新一次最远坐标。
这里用了双指针的做法进行解答。
class Solution {public ListInteger partitionLabels(String s) {ListIntegerlistnew ArrayList();MapCharacter,Integermnew HashMap();if(s.length()0)return list;for(int is.length()-1;i0;i--){m.put(s.charAt(i),m.getOrDefault(s.charAt(i),i));}int l0;int r0;int indexm.get(s.charAt(l));while(rs.length()){if(rs.length()-1rindex){list.add(r-l1);lr1;rl;}else{r;}if(rs.length())indexMath.max(index,m.get(s.charAt(r)));}list.add(r-l);return list;}
}
