字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例:
- 输入:S = "ababcbacadefegdehijhklij"
- 输出:[9,7,8] 解释: 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少
之前在回溯部分,有用回溯算法分割过字符串,但是属于暴力搜索,时间复杂度较高。
题目要求同一字母最多出现在一个片段中,并且划分尽可能多的片段,那么如何把同一个字母的都圈在同一个区间里呢?就是找到出现过的字母的最大终止位置。
可以分为如下两步:
- class Solution {
- public List
partitionLabels(String s) { - LinkedList
list=new LinkedList<>(); - int[] edge=new int[26];
- char[] chars=s.toCharArray(); //将一个字符串转换成一个字符(char)数组。
- //比如abecadf 那么edge[0]存储的就是a出现的次数
- for(int i=0;i
- edge[chars[i]-'a']=i; //统计每个字符出现的最后位置 ,按照字母的顺序存储
- }
- int idx=0, last=-1;
- for(int i=0; i
- idx=Math.max(idx, edge[chars[i]-'a']); //遍历出现过的元素,更新最远位置
- if(i==idx){ //如果已经走到了前面出现过的覆盖的最远位置
- list.add(i-last);// 记录当前子串的长度
- last=i; //更新起点
- }
- }
- return list;
- }
- }
56. 合并区间
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
- 输入: intervals = [[1,4],[4,5]]
- 输出: [[1,5]]
- 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
- 注意:输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
依旧是重叠区间问题,先按照start排序,再进行重叠判断,本题相邻区域也算重叠,因此若intervals[i][0]<=intervals[i-1][1],则有重叠。若有重叠,则将区间的左右边界判断更新end使之成为两个区间的最远end,加入result数组,若不重合,更新start和end,直接加入原区间。
- class Solution {
- public int[][] merge(int[][] intervals) {
- List<int[]> res=new LinkedList<>();
- Arrays.sort(intervals, (a,b)->Integer.compare(a[0], b[0]));
- int start=intervals[0][0];
- int end =intervals[0][1];
- for(int i=1;i
- if(intervals[i][0]>end){//不重叠
- res.add(new int[]{start, end});//将当前节点加入res
- start=intervals[i][0]; //更新start
- end=intervals[i][1];
- }else{
- end=Math.max(end, intervals[i][1]); //更新最大右边界
- }
- }
- res.add(new int[]{start, end});
- return res.toArray(new int[res.size()][]);
- }
- }
这里要注意一个语法基础⚠️在链表list里面添加值,然后把list链表添加进res链表中,在做算法题的时候,如果使用res.add(list)
,输出打印为空,因此需要res.add(new LinkedList<Integer>(list))。同理,在这里如果想要给链表res添加新的数组,一定也要res.add(new int[]{start, end});
-
相关阅读:
分布式存储系统之Ceph集群RBD基础使用
wsl kali-linux 安装记录
常见的状态码即问题解决
如何编辑图片合成图片?让我们来看看这些合成方法
Spring中的面试题01
代码随想录Day18 LeetCode235 二叉搜索树的公共祖先 T701二叉搜索树中的插入操作 T140 删除二叉搜索树中的公共节点
ios ipa包上传需要什么工具
数据提取-数据提取软件
pcl基于颜色的区域增长点云分割
伪装目标检测与分割研究进展
-
原文地址:https://blog.csdn.net/weixin_36675391/article/details/136385227