435. 无重叠区间
题目链接
https://leetcode.cn/problems/non-overlapping-intervals/description/
题目描述
思路
直接统计重叠区间的个数，就是需要删除的个数
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));
if(intervals.length == 0) return 0;
int count = 0;
for (int i = 1; i < intervals.length; i++) {
//当前左区间小于上一个的右区间，就表明两个是互相重叠的
if(intervals[i][0] < intervals[i-1][1]){
count++;
intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);
}
}
return count;
}
763.划分字母区间
题目链接
https://leetcode.cn/problems/partition-labels/description/
题目描述
思路
对于上边的字符串 s = “ababcbacadefegde”
最开始先包含 a ,根据题目要求，需要把所有的 a 都囊括进一个区间里边，所以找到最远的 a 为下标 8 的位置，但是在囊括 a 的同时，需要把 b c 囊括进来，所以需要再次找 b c 的最远位置，统计过 a b c 的最远位置之后进行比较，这一个区间的最远位置就是 8 ，因此 8 之前就为一个分割区间
class Solution {
public List<Integer> partitionLabels(String s) {
ArrayList<Integer> list = new ArrayList<>();
//先统计每个字符出现的最远位置
//遍历字符串
int[] hash = new int[26];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a'] = i;
}
//定义区间的左右边界
int left = 0,right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right,hash[s.charAt(i) - 'a']);
//i==right 说明已经到了这个字符串的最右边
if(i==right){
//将长度加到结果列表中
list.add(right-left+1);
left = i+1;
}
}
return list;
}
}
56. 合并区间
题目链接
https://leetcode.cn/problems/merge-intervals/description/
题目描述
思路
思路在代码注释中均有描述
public int[][] merge(int[][] intervals) {
//存放最后的结果
ArrayList<int[]> list = new ArrayList<>();
if(intervals.length==0) return new int[0][];
//按照左边界进行排序
Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
list.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if(intervals[i][0] <= list.get(list.size()-1)[1]){
//说明重叠了，需要进行合并
//区间的最小边界肯定是已经存进去的左边界，所以不用做更新
//需要更新右边界，将当前元素和已经存进去的右边界进行比较，取大的一方
list.get(list.size()-1)[1] = Math.max(intervals[i][1],list.get(list.size()-1)[1]);
}else {
//没有重叠，直接添加到结果中，不做任何操作
list.add(intervals[i]);
}
}
return list.toArray(new int[list.size()][]);
}