青岛做网站的公司有哪些,网站设计入门,学软件开发需要什么基础,wordpress 翻译制作题目要求#xff1a;
将字符串 s 划分成尽量多的片段#xff0c;保证每个片段中出现的字母不会出现在其他片段中。
具体解释如下#xff1a; 尽量多的片段#xff1a;题目要求的是在划分过程中#xff0c;我们要尽量让划分的片段数量最大化#xff0c;而不是最少化。每…
题目要求
将字符串 s 划分成尽量多的片段保证每个片段中出现的字母不会出现在其他片段中。
具体解释如下 尽量多的片段题目要求的是在划分过程中我们要尽量让划分的片段数量最大化而不是最少化。每次划分的片段应当符合下述条件。 字母不会出现在其他片段中对于每个划分出的片段片段中的每个字母只能在该片段内出现不能在其他片段中再出现。换句话说每个字母都必须包含在一个完整的片段中且不能跨越多个片段。
划分过程
为了满足这个要求划分的基本思路是
从头开始遍历字符串对于当前遇到的字符找到它在字符串中最后一次出现的位置。继续遍历更新片段的结束位置当前片段中所有字符的最远出现位置。当遍历到的字符索引正好是该片段的结束位置时就可以划分出一个片段。然后继续处理剩下的字符串直到整个字符串都被划分完毕。
这种做法能保证每个片段中的所有字母都只出现在这个片段中同时也能保证片段数量是最多的。
举个例子
对于字符串 s ababcbacadefegdehijhklij划分过程如下 从第一个字符 a 开始找到 a 的最后出现位置是索引 8同时还要考虑字符 b 和 c 的最后出现位置是索引 5 和 7。因此第一个片段应该是从索引 0 到索引 8片段为 ababcbaca。 接着从索引 9 开始处理下一个字符 d找到 d 的最后出现位置是索引 14字符 e 的最后位置是索引 15。所以第二个片段是从索引 9 到索引 15片段为 defegde。 最后处理从索引 16 开始的部分字符 h、i、j 的最后出现位置分别是索引 19、22 和 23。因此第三个片段是从索引 16 到索引 23片段为 hijhklij。
因此最终的划分结果为[9, 7, 8]即 ababcbaca、defegde 和 hijhklij。
这种划分方式能确保每个片段中的字母不会出现在其他片段中并且片段的数量是最大化的。
java solution
class Solution {public ListInteger partitionLabels(String s) {ListInteger result new ArrayList();int[] lastIndex new int[26];//统计 s 中每个字符的最后出现位置下标for(int i 0; i s.length(); i) {lastIndex[s.charAt(i) - a] i;}int start 0, end 0;for(int i 0; i s.length(); i) {//先根据当前字符的最后出现位置下标更新endend Math.max(end, lastIndex[s.charAt(i) - a]);if(i end) {result.add(end - start 1);start end 1;}}return result;}
}
