您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

LeetCode:区间类题目总结

开发技术 168℃ 0 2个月前 (04-04)

摘要

LeetCode:区间类题目总结

通用思路

1、区间的定义:二维数组,每个元素长度为2,分别表示起始和终止点。

int[][] intervals;

2、将区间按照起始点从小到大排序(或者按照终止点排序)。

// anonymous class
Arrays.sort(intervals, new Comparator<>() {
    public int compare(int[] a, int[] b) {
        return a[0] - b[0];
    }
});

// lambda expression
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);

3、循环遍历处理区间,前一个区间为蓝色,后一个区间为绿色,两者有如下三种情况。

56. 合并区间

题目

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解答

合并区间取并集。

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        // sort by start from small to large
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        List<int[]> result = new LinkedList<>();
        int[] pre = intervals[0];
        for (int i = 1; i < intervals.length; ++i) {
            int[] cur = intervals[i];
            // Case I: pre[0] < pre[1] < cur[0] < cur[1]: add new
            if (cur[0] > pre[1]) {
                result.add(pre);
                pre = cur;
            }
            // Case II: pre[0] < cur[0] < cur[1] <= pre[1]: merge
            else if (cur[1] <= pre[1]) {
                // do nothing
            }
            // Case III: pre[0] < cur[0] <= pre[1] < cur[1]: merge
            else {
                pre[1] = cur[1];
            }
        }
        result.add(pre);
        return result.toArray(new int[0][0]);
    }
}

452. 用最少数量的箭引爆气球

题目

在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后,可以无限地前进。我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。

Example:

输入:
	[[10,16], [2,8], [1,6], [7,12]]

输出:
	2

解释:
	可以用2支箭,x = 6(射爆[2,8],[1,6]两个气球)和 x = 11(射爆另外两个气球)。

解答

合并区间取交集。合并后的每个重叠区间范围内用一支箭(注意,重叠区间的起点和终点可以相同)。

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        // sort by start from small to large
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        int[] pre = points[0];
        // no need to save merge results, just counting
        int count = 1;
        for (int i = 1; i < points.length; ++i) {
            int[] cur = points[i];
            if (cur[0] > pre[1]) {
                // Case I: pre[0] <= pre[1] <= cur[0] <= cur[1]: add new
                ++count;
                pre = cur;
            } else if (cur[1] <= pre[1]) {
                // Case II: pre[0] <= cur[0] <= cur[1] <= pre[1]: merge
                pre[0] = cur[0];
                pre[1] = cur[1];
            } else {
                // Case III: pre[0] <= cur[0] <= pre[1] < cur[1]: merge
                pre[0] = cur[0];
            }
        }
        return count;
    }
}

435. 无重叠区间

题目

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

  • 可以认为区间的终点总是大于它的起点。
  • 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

解答

删除区间。贪心思想,遍历区间,每次遇到重叠时删除end更大的区间,尽可能避免其与下一个区间的start发生重叠。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return 0;
        }
        // sort by start from small to large
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        int delete = 0;
        int[] pre = intervals[0];
        for (int i = 1; i < intervals.length; ++i) {
            int[] cur = intervals[i];
            // pre[0] < pre[1] <= cur[0] < cur[1]: merge pre, pre = cur, not delete
            if (cur[0] >= pre[1]) {
                pre = cur;
            }
            // pre[0] < cur[0] < pre[1] < cur[1]: delete cur
            else if (cur[1] > pre[1]) {
                delete++;
            }
            // pre[0] < cur[0] < cur[1] < pre[1]: delete pre, pre = cur
            else {
                pre = cur;
                delete++;
            }
        }
        return delete;
    }
}

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/leetcode-intervals
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?