在这里插入图片描述


   一:用最少数量的箭引爆气球

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

   题目描述:有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组points,其中points[i] = [Xstart,Xend]表示水平直径在Xstart和Xend之间的气球。你不知道气球的确切y坐标。

   一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标(x处射出一支箭,若有一个气球的直径的开始和结束坐标为Xstart , Xend,且满足Xstart ≤ X ≤ Xend,则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后,可以无限地前进。
给你一个数组points ,返回引爆所有气球所必须射出的最小弓箭数。

   示例 1:

输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8][1,6]-在x = 11处发射箭,击破气球[10,16][7,12]

   示例 2:

输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。

   示例 3:

输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2][2,3]- 在x = 4处射出箭,击破气球[3,4][4,5]

   提示:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= xstart < xend <= 2^31 - 1

   解题思路:

   ① 看到这道题,最先想到的是,直接按照每个区间的右端点进行排序,然后从头开始遍历排序后的队列。

   ② 此时队列中第一个元素的右端点,就是整个队列最靠左的右端点right,想要射掉该气球,必然要在right之前射一箭,同时这一箭会射掉所有左端点在射箭处或射箭处之前的所有气球,很显然,根据贪心的思想,射箭处选在最靠右的right处,射掉的气球最多。 所以,每次射箭点,必然选取在某个区间的右端点处。这些射掉的气球将被从队列中移除。本次射箭结束,射箭次数加1。

   ③ 重复执行上面的步骤②,直至队列为空,所有气球都被射掉了

   上述思路的参考程序如下:

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        // 因为涉及到大量的删除操作,为了将每个元素删除操作的时间复杂度
        // 从vector的O(n)降为list的O(1), 所以将 vector 转换为 list       
        list<vector<int>> points_list(points.begin(), points.end());
        int ans=0;
        while(!points_list.empty())
        {   
            // 注: list 是一个链表结构,不支持随机访问,这意味着你无法直接通过索引访问其元素。
            // points_list[0][1]是不被允许的
            int right=points_list.front()[1];   
            for(auto it= points_list.begin();it!=points_list.end();)
            { 
                if((*it)[0]<=right)  //注意:这里的(*it)中的()不能忽略,要先解引用得到vector<int>类型,再取其第一个元素
                {
                  it = points_list.erase(it); // 删除元素,并立即更新迭代器到下一个元素
                }
                else
                {
                    ++it; // 只有在不删除的情况下才手动递增迭代器
                }
            }

            ans++;
        }
        return ans;
    }
};

   上面的程序,有几点需要注意:

   1、由于程序中涉及大量的删除操作,vector容器的每进行一次删除操作时间复杂度是O(n),很容易超时,因此,上面程序中在进行删除之前,将存放数据的容器更改为了list,list删除一个元素的时间复杂度是O(1)

   2、list 底层实现是链表结构,不支持随机访问,这意味着无法直接通过索引访问其元素。即,无法像vector那样使用 points_list[0][1]来访问points_list中的第一个元素,需要使用points_list.front()[1]来访问;


   改进解题思路:

   上面将被射掉的气球从队列中删除的思路,容易我们理解, 但是删除操作是很费时的,其实,我们完全没必要将其删除。

   按照右端点排序后,依然从头开始遍历排序后的队列,每轮射箭同样取队列中当前气球 (注意:因为不再进行删除,所以这里是根据索引值取的气球,除了第一次射箭外,不再是取第一个) 的右端点作为界限, 然后,若后面气球的左端点<=界限,则直接跳过(不再像之前那样将其从容器中移除了) ,若左端点>界限,则射箭数+1,并将该气球的右端点作为新的界限,循环执行以上过程。直至遍历结束

   上述改进思路的参考程序如下:

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int ans=0,i=0;
        while(i<points.size())
        {
            int right=points[i][1];
            while( i<points.size() && points[i][0]<=right ) {i++;} 
            ans++; 
        }
        return ans;
    }
};

   其实,这道 用最少数量的箭引爆气球 的题,本质上就是在找给定的这一系列区间中的互不重叠的区间个数,需要特别注意的是,本题中设定l两个区间,仅某个端点重合时,也是重合的,例如区间[1,3] 和[3,4]是重合的,所以程序中points[i][0]<=right是带等于号的。


在这里插入图片描述


   二:无重叠区间

   435. 无重叠区间

   题目描述:给定一个区间的集合 intervals,其中每个 intervals[i] = [starti, endi],求需要移除区间的最小数量,使得剩余区间不重叠。

   示例 1:

  • 输入:intervals = [[1,2], [2,3], [3,4], [1,3]]
  • 输出:1
  • 解释:移除区间 [1,3] 后,剩下的区间不重叠。

   示例 2:

  • 输入:intervals = [[1,2], [1,2], [1,2]]
  • 输出:2
  • 解释:你需要移除两个 [1,2] 来保证剩下的区间不重叠。

   示例 3:

  • 输入:intervals = [[1,2], [2,3]]
  • 输出:0
  • 解释:你不需要移除任何区间,因为它们已经是互不重叠的了。

   提示:

  • 1 <= intervals.length <= 10^5

  • intervals[i].length == 2

  • -5 * 10^4 <= starti < endi <= 5 * 10^4

   解题思路:

   看到这道题有没有很熟悉的感觉,其实他跟上面那道射气球的题是高度类似的,我在射气球那道题最后说了,最少射箭次数 其实就是在找互不重叠的区间个数,这道题找的是需要移除的区间数量,即,给定区间数量-互不重叠的区间个数。所以,有了之前的基础,这道题直接秒就可以了。

   但是需要注意的是,射气球那道题认为一个区间的右端点跟另一个区间左端点重合 算重叠区间,而这道题算不重叠区间,所以要去掉等于号:intervals[i][0]<right

   两道题的程序,仅存在两处细小的差异:

在这里插入图片描述

   容易得到参考程序如下:

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[1]<b[1]; }
   
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int ans=0,i=0;
        while(i<intervals.size())
        {
            int right=intervals[i][1];
            while( i<intervals.size() && intervals[i][0]<right ) {i++;} 
            ans++; 
        }
        return intervals.size()-ans;
    }
};

在这里插入图片描述



   三:合并区间

   56. 合并区间

   题目描述:以数组 points表示若干个区间的集合,其中单个区间为 points[i] = [starti, endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需要恰好覆盖输入中的所有区间。

   示例 1:

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

   示例 2:

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

   提示:

1 <= points.length <= 10^4
points[i].length == 2
1 <= starti <= endi <= 10^4

   解题思路:

   有了前面射气球那道题的基础,这道题同样可以快速秒了,思路都差不多,如下所示:

   ① 首先按照每个区间的左端点进行排序,然后从头开始遍历排序后的队列。

   ② 此时队列中第一个元素的左端点,就是整个队列最靠左的左端点left,且其右端点为right,遍历后续区间,若该区间的左端点小于right,必然是重叠区间,若当前区间的右端点大于right,此时需要对right更新,因为right存放的就是当前所有重叠区间的最右边界。继续遍历下一个,直至遍历到的区间的左端点大于right,说明当前遍历到的区间与前面遍历的所有区间均不重合。此时将{left,right}压入结果队列中,即前面所有重叠区间合并后的左右界限。然后将当前遍历到的区间的左右端点分别赋值给left,right,继续重复以上过程,遍历后续区间,直至所有区间遍历完成。

   容易得到参考程序如下:

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)  { return a[0]<b[0]; }
   
    vector<vector<int>> merge(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        vector<vector<int>> ans; int i=0;
        while(i<points.size())
        {   
            int left=points[i][0];
            int right=points[i][1];
            while( i<points.size() && points[i][0]<=right ) 
            {   
                if(points[i][1]>right) right=points[i][1];
                i++;
            } 
            ans.push_back({left,right});
        }
        return ans;
    }
};

在这里插入图片描述


点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部