0%

每日三题 leetcode 435 无重叠区间 leetcode 452 用最少的箭引爆气球 leetcode 1110 删点成林

发表于 分类于 ， ， 评论次数:：
本文字数： 3.3k 阅读时长 ≈ 3 分钟

leetcode 435 无重叠区间

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

注意:

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

1
2
3
4
5
6
示例 1:

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

解释: 移除 [1,3] 后，剩下的区间没有重叠。
1
2
3
4
5
6
示例 2:

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

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

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

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

思路：经典区间贪心，考虑一下几种情况：
覆盖

相交

覆盖时显然要选[x2,y2]因为这段可以容纳的无重叠区间更宽，而相交时，对于虚线右边来说是没有跟它相交的，只要找到右端点不与x2重叠的x3即可，上一段的左端点更新为新的左端点x3。所以将所有区间按照左端点从大到小排列后贪心找出不重叠的区间即可,因为要找到移除的区间所以用总区间个数减去不重叠的区间个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if(!n) return 0;
        sort(intervals.begin(),intervals.end(),[&](const vector<int> &p1,const vector<int> &p2){
            return p1[0] == p2[0] ? p1[1] < p2[1] : p1[0] > p2[0];
        });
        int ans = 1, last = intervals[0][0];
        for(int i=1;i<n;i++){
            if(last >= intervals[i][1]){
                ans++;
                last = intervals[i][0];
            }
        }
        return n - ans;
    }
};

leetcode 452 用最少的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

1
2
3
4
5
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
1
2
3
4
示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
1
2
3
4
示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
1
2
3
4
示例 4：

输入：points = [[1,2]]
输出：1
1
2
3
4
示例 5：

输入：points = [[2,3],[2,3]]
输出：1

提示：

  1. $0 <= points.length <= 10^4$
  2. $points[i].length == 2$
  3. $-2^{31} <= xstart < xend <= 2^{31} - 1$

思路：跟上题思路差不多，只不过当上一个区间的左端点与当前区间右端点重合时不需要更新答案，因为可以在重合的边界处同时引爆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if(!n) return 0;
        sort(intervals.begin(),intervals.end(),[&](const vector<int> &p1,const vector<int> &p2){
            return p1[0] == p2[0] ? p1[1] < p2[1] : p1[0] > p2[0];
        });
        int ans = 1, last = intervals[0][0];
        for(int i=1;i<n;i++){
            if(last > intervals[i][1]){
                ans++;
                last = intervals[i][0];
            }
        }
        return ans;
    }
};

leetcode 1110 删点成林

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

树

1
2
3
4
示例：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

思路：因为先序遍历可以先访问根节点，所以可以在做先序遍历的时候添加答案，但是这样会有问题，假如当前节点不用删除，先序访问到当前节点时要加入答案中，但是如果该节点的祖先节点中如果已经加入答案中了，这个节点就重复加入了，所以在递归的时候要引入一个标记位来标记当前节点能不能被加入答案中，1表示可以加，0表示不可加，如果一个节点要被删除，那么它的子节点就有加入答案数组中的机会了，所以要重置标记为1，再删掉这个点，因为每个节点值都不同，所以可以用一个哈希表来记录节点是否删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool hash[1001];
    vector<TreeNode*>res;
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for(int &c:to_delete) hash[c] = 1;
        dfs(root,1);
        return res;
    }
    void dfs(TreeNode* &root,bool flag){
        if(!root) return ;
        TreeNode* &l=root->left, *&r = root->right;
        if(hash[root->val]) flag = 1, root = nullptr;
        else 
            if(flag) res.push_back(root), flag=0;
        dfs(l,flag);
        dfs(r,flag);
    }
};