Partition Labels-面试题

本文主要是介绍Partition Labels-面试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目:分割字符串使得同种字符分隔到一起

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
给出一个小写字母的字符串。我们希望将这个字符串划分为尽可能多的部分，以便每个字母最多出现在一个部分中，并返回表示这些部分大小的整数列表。
Example：Input: S = “ababcbacadefegdehijhklij Output: [9,7,8]

题目分析

贪心算法
S中最左边的一组一定包含第一个字母的全部，以第一个字母的最大索引为分割点，依次比较第一组中的所有字母的最大索引，如果比分割点的索引大，则更换分割点，分割点前的所有字母数目即为输出的第一个数
第一组确定之后，将分割点后的第一个字母作为新一轮的第一个字母，继续上述的步骤

Java代码

class Solution {public List<Integer> partitionLabels(String S) {if(S.length()==0)return null;List<Integer> list = new ArrayList<>();//采用list存储结果，list不定长，利用add方法在链表后添加元素int[] word = new int[26];for(int i = 0;i<S.length();i++){word[S.charAt(i)-'a']=i;//word数组用来存储每个字母的最大索引}int start = 0,end = 0;//标记分割成小组的开始索引和结束索引for(int i=0;i<S.length();i++){//遍历S中的所有字母end = Math.max(end,word[S.charAt(i)-'a']);//将结束索引与遍历的字母的最大索引比较大小，取最大的值作为该小组的最大索引if(end==i){//当遍历到这个最大索引时，证明其左边字母的全部均包含在内，该索引点即为分割点list.add(end-start+1);start=end+1;//开始点为分割点的下一个字母，进行下一步的遍历}}return list;}
}