没建网站 备案,wordpress内容采集,邯郸做网站服务商,做甜点的网站435. 无重叠区间 我认为区间类的题型#xff0c;大多数考验的是思维能力#xff0c;以及编码能力#xff0c;该类题型本身并无什么算法可言#xff0c;主要是思维逻辑#xff0c;比如本题实际上你只需要能够总结出重叠与不重叠的含义#xff0c;再加上一点编码技巧#…435. 无重叠区间 我认为区间类的题型大多数考验的是思维能力以及编码能力该类题型本身并无什么算法可言主要是思维逻辑比如本题实际上你只需要能够总结出重叠与不重叠的含义再加上一点编码技巧便可完成。
解题思路
正如前面所说那么解题的关键思路就在于找到重叠区间的特性即可我们不妨先按照start进行一次排序再进行观察比如数组[[1,2],[2,3],[3,4],[1,3]]排序后为[[1,2],[1,3],[2,3],[3,4]]通过观察我们很容易发现如果前一个数组的end大于下一个数组的start则这两个数组一定发生了重叠这个比较容易理解如图所示分别有两个数组[1,2]和[1,3] 重叠部分一眼可见但关键在于产生重叠后应该留下谁舍弃谁我们不妨还是画图理解按照题目示例接下来一组数字是[2,3] 我们可以分开讨论假设我们选择保留[1,3]那么很明显下一组[2,3]将变为重叠部分。 而如果我们选择保留[1,2]则不会再产生重叠部分。
根据题目要求需要我们通过移除最少的区间数量来实现区间互不重叠因此应当使用第二种方案从原理上来说就是当两个区间产生重叠后我们应当保留区间范围更小的一组因为这样更有可能避免与后面的区间再产生重叠很容易理解的一点概念区间范围越大越容易发生重叠 结论假设有[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]如果e1 s2则将触发[s1 ,e1],[s2, e2]合并合并规则为如果e1 e2合并为[s1, e2]否则合并为[s1, e1]如果e1 s2则无需合并直接检查下一个区间即可。 代码实现
public int eraseOverlapIntervals(int[][] intervals) {// 不要忘了先按start进行排序Arrays.sort(intervals, (o1, o2) - o1[0] - o2[0]);int ans 0;int end intervals[0][1];for(int i 1; i intervals.length; i){int start intervals[i][0];if(end start){end Math.min(end, intervals[i][1]);ans;}else{end intervals[i][1];}}return ans;
} 56. 合并区间 解题思路
本题与上一题比较相似都是处理重叠区间的问题我们同样可以画图理解以题目示例1为例[[1,3],[2,6],[8,10],[15,18]]。 首先与前一题一样如果前一个数组的end大于下一个数组的start则表示一定出现了重叠而关于end部分的去留则正好与前一题相反前一题保留的是较小部分本题则需要保留较大部分。 结论假设有[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]如果e1 s2则将触发[s1 ,e1],[s2, e2]合并合并规则为如果e1 e2合并为[s1, e1]否则合并为[s1, e2]如果e1 s2则无需合并直接检查下一个区间即可。 代码实现
由于本题需要在原数组上进行修改因此先借用一个list辅助记录实际处理逻辑并没区别。
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (o1, o2) - o1[0] - o2[0]);Listint[] list new ArrayList();list.add(new int[]{intervals[0][0], intervals[0][1]});for(int i 1; i intervals.length; i){int start intervals[i][0];int end intervals[i][1];if(list.get(list.size()-1)[1] start){list.add(new int[]{start, end});}else{list.get(list.size()-1)[1] Math.max(end, list.get(list.size()-1)[1]);}}return list.toArray(new int[list.size()][]);}
}1288. 删除被覆盖区间 解题思路
前面两题处理的都是数据范围重叠的问题本题要解决的则是数据范围覆盖问题我们先要搞清楚符合覆盖的条件有哪些很明显当s1 s2 且 e2 e1时则认为[s2, e2]区间被[s1, e1]区间覆盖。
如下图所示 结论假设有[[s1, e1], [s2, e2], [s3, e3] ... [sn, en]]当s1 s2 且 e2 e1时则可删除区间[s2, e2]这里需要注意的是为了方便处理我们可以让start按照升序排序的同时并让end按照降序排序这样代码实现时只要满足e1 e2即可认为被覆盖了。实际上就是为了方便进行判断s1 s2 且 e2 e1 代码实现
class Solution {public int removeCoveredIntervals(int[][] intervals) {Arrays.sort(intervals, (o1, o2) - o1[0] o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);int cnt 0;int preEnd intervals[0][1];for (int i 1; i intervals.length; i) {int curEnd intervals[i][1];if (preEnd curEnd) {cnt;} else {preEnd curEnd;}}return intervals.length - cnt;}
}
