代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间 、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()][]);
}