广州h5网站建设,青岛建站方案,国外做美食的网站,泰安房产网新楼盘目录 1.题目2.思路3.代码实现#xff08;Java#xff09; 1.题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段#xff0c;同一字母最多出现在一个片段中。注意#xff0c;划分结果需要满足#xff1a;将所有划分结果按顺序连接#xff0c;得到的字符串仍… 目录 1.题目2.思路3.代码实现Java 1.题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。
示例 1 输入s “ababcbacadefegdehijhklij” 输出[9,7,8] 解释 划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。
示例 2 输入s “eccbbbbdec” 输出[10]
提示 1 s.length 500 s 仅由小写英文字母组成
2.思路
1贪心算法
3.代码实现Java
//思路1————贪心算法
class Solution {public ListInteger partitionLabels(String s) {int length s.length();ListInteger res new ArrayList();//记录每个字母在 s 中最后依次出现的下标int[] lastPos new int[26];for (int i 0; i length; i) {int index s.charAt(i) - a;lastPos[index] i;}int start 0;int end 0;for (int i 0; i length; i) {end Math.max(end, lastPos[s.charAt(i) - a]);//当前字母在 s 中最后一次出现的下标等于 i则说明片段 s[start...end] 可以被划分出来if (i end) {res.add(end - start 1);start i 1;}}return res;}
}
