文章目录
- 重叠问题
- 435. 无重叠区间
- 763.划分字母区间:star:
- 56. 合并区间
重叠问题
这几道题都是判断区间重叠,区别就是判断区间重叠后的逻辑。
435. 无重叠区间
-
链接:代码随想录
-
解题思路:
这道题和射气球的题几乎思路一样
不断求出重叠的最小右区间,模拟重叠过程就可解题
public int eraseOverlapIntervals(int[][] intervals) {
//按左边排序
Arrays.sort(intervals, (a,b)->{
return Integer.compare(a[0], b[0]);
});
int remove = 0;//该移除的区间
int pre = intervals[0][1];//前一个判断的右区间
for (int i = 1; i < intervals.length; i++) {
//有重叠的情况
if(pre > intervals[i][0]){
remove++;
//更新最新的右区间为
//相交的时候去最小的右边,没被取的右边的区间即被删除
pre = Math.min(pre, intervals[i][1]);
}else{
pre = intervals[i][1];//没有重叠的情况
}
}
return remove;
}
763.划分字母区间⭐️
-
链接:代码随想录
-
解题思路:
①统计每一个字符最后出现的位置**(哈希结构存储)**
②从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点 贪心可能体现在,找最远下标的情况
用最远出现距离模拟了圈字符。
如果遍历的 i == 最远下标,说明之前遍历过的元素都符合划分范围,即划分 -
图像理解
public List<Integer> partitionLabels(String s) {
int[] hash = new int[26];//hash[i] 为字符最远出现的地方的索引 用哈希结构维护(索引 -- 值)
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a'] = i;
}
int left = 0;//每一次区间的起点位置
int right = 0;//每一次划分区间的末尾位置
List<Integer> res = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, hash[s.charAt(i) - 'a']);//取最大边界
//遍历到最大边界
if(i == right){
res.add(right - left + 1);
left = right + 1;//更新起点位置
}
}
return res;
}
56. 合并区间
- 题目链接:代码随想录
重叠问题
-
解题思路:
此题判断重叠区间还是原先的思路,先排序,再根据右边界和左边界进行判断
关键点在于判定重叠区间后,判断进行加入结果集的操作 -
图像理解:
public int[][] merge(int[][] intervals) {
List<int[]> res = new LinkedList<>();//结果集
//1.排序
Arrays.sort(intervals,(a,b) -> {
return Integer.compare(a[0], b[0]);
});
//2.定义区间,来求最大重叠区域,并处理最大重叠区域,添加进一个新的结果集,耗空间
int start = intervals[0][0];//起始位置
int right = intervals[0][1];//右区间
//3.进行遍历
for (int i = 1; i < intervals.length; i++) {
//重叠区域,更新最大右区间,先不加入结果集
if(right >= intervals[i][0]){
right = Math.max(right, intervals[i][1]);
}else{//非重叠区域,将非重叠的第一个区域加入结果集,符合要求
res.add(new int[]{start,right});//前一个位置
//更新当前区间
start = intervals[i][0];
right = intervals[i][1];
}
}
//最后一定要加入最后一个待加入区间
res.add(new int[]{start,right});
return res.toArray(new int[res.size()][]);
}