婚纱设计网站首页,健康东莞app,南京网站开发联系南京乐识,wordpress修改样式表题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。
注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。…题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。 示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。 思路
1.由于一个字母只能出现在同一片段—— 同一个字母的第一次出现的下标位置和最后一次出现的下标必须出现在同一个片段 —— 遍历字符串得到每个字母最后一次出现的下标位置
2.在步骤1之后采用贪心算法将字符串划分尽可能多的片段
从左到右遍历String同时维护当前片段的开始下标start和结束下标end 【初始时 start end】对于每个访问到的字母c得到其最后一次出现的下标位置endcendmax(end,endc)当访问到下标endc时当前片段访问结束 下标范围【startend】,长度 end - start 1将当前片段的长度添加到返回值中然后另start end 1,继续寻找下一个片段 代码
class Solution {public ListInteger partitionLabels(String s) {// 创建一个长度为26的数组用于存储每个字符最后出现的位置int[] last new int[26];int n s.length();for(int i 0; i n; i){// 更新对应字符的最后出现位置last[s.charAt(i) - a] i;}// 创建一个列表 用于存储分割的字符串的长度ListInteger result new ArrayList();int start 0;int end 0;for(int i 0; i n; i){// 更新结束位置 即未当前字符最后出现的位置end Math.max(end, last[s.charAt(i) - a]);// 如果当前位置等于结束位置说明已经找到了一个连续的相同字符子串if(i end){result.add(end - start 1);start end 1;}}// 返回最终结果return result;}
}
