贪心---划分字母区间 Posted on 2021-08-19 00:00:00 2021-08-19 00:00:00 by Author 摘要 给定一个字符串,你能尽可能把这个字符串划分为尽可能多的片段,使其同一字母最多出现在一个片段中??? # 贪心---划分字母区间 1. 题目描述 - 字符串 `S` 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 - **提示:** - `S`的长度在`[1, 500]`之间。 - `S`只包含小写字母 `'a'` 到 `'z'` 。 2. 示例描述 - 示例一 ```java 输入:S = "ababcbacadefegdehijhklij" 输出:[9,7,8] 解释: 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。 ``` - 示例二 ```java 输入:S = "abcabcghjkjgo" 输出:[6,6,1] ``` 3. 解题思路 - 首先对于本题来说,我们可以找到所给定字符串中每个字最后出现的位置。这里可以使用桶原理去做。 - 其次遍历整个字符串,对于字符串里的第一个字符来说,它最后出现的位置为x,那么0到x之间有其他字符,如果之间的字符的最后出现位置比这个x大,那么说明中间的这个字符和第一个字符是同一个区间的,那么x就要变为本区间字符最后出现位置的最大位置。如果遍历的变量下标刚好和本区间字符最后出现的位置相等,那么说明这个区间里面的所有字符都在同一个区间了,后面出现的字符不会出现在这个区间了,如果出现在这个区间了,那么这个区间字符中最后出现位置的最大值就不是遍历的下标值了,这样就能划分一个区间,然后循环按照这个步骤进行操作,直到遍历完整个字符串,那么划分区间也就完成。 - 具体代码示例如下,这个可以手动实现一遍,效果更好的。 4. 代码示例 ```java public List<Integer> partitionLabels(String S) { List<Integer> result=new ArrayList<>(); if(S.length()<=0){ return result; } //构建一个桶数组 int bucket[]=new int[26]; //字符串转化为字符数组方便后续操作 char chars[]=S.toCharArray(); //查找每个字符最后出现的位置 for (int i=0;i<S.length();i++){ bucket[chars[i]-'a']=i; } //left表示每个区间的起始位置,right表示每个区间的终点位置 int left=0,right=0; for (int i = 0; i < chars.length; i++) { //贪心思想,找到最大的区间 right=Math.max(bucket[chars[i]-'a'],right); //如果最大的区间已经和遍历的下标相等了那说明本次划分区间已经结束了 //因为之前的所有字符的最大区间已经到此结束了,那么后续的字符肯定不会出现在前面字符集合中 if(i==right){ //同一区间的字符长度加入集合中 result.add(right-left+1); //同时left变更到该位置的下一个坐标的位置 left=i+1; } } //返回最终的结果 return result; } ```
{{ item.content }}
{{ child.content }}