首页 > 其他分享 >452. 用最少数量的箭引爆气球

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

时间:2024-09-02 15:52:43浏览次数:9  
标签:支箭 引爆 452 points xstart xend 气球

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

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstartxend, 且满足  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]。

题解

这里思路的话,可以看下官方的题解,和435题类似(先排序再按照贪心策略求解)

考虑所有气球中右边界位置最靠左的那一个,那么一定有一支箭的射出位置就是它的右边界(否则就没有箭可以将其引爆了)。当我们确定了一支箭之后,我们就可以将这支箭引爆的所有气球移除,并从剩下未被引爆的气球中,再选择右边界位置最靠左的那一个,确定下一支箭,直到所有的气球都被引爆。

代码

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),
        [](vector<int> &x,vector<int> &y)->bool{
            if(x[1]==y[1])
                return x[0]<y[0];
            return x[1]<y[1];
        });
        int i,j,count=0;
        int size=points.size();
        for(i=1,j=0;i<size;i++){
            while(i<size&&points[i][0]<=points[j][1]){//范围有交叉就会引爆气球
                i++;
            }
            count++;
            j=i;
        }
        if(j==size-1)//当j为最后一项时,i不满足循环条件,for循环会提前退出,而没有将数量加一
            count++;
        return count;
    }
};

标签:支箭,引爆,452,points,xstart,xend,气球
From: https://blog.csdn.net/qq_33811080/article/details/141821917

相关文章

  • 452. 用最少数量的箭引爆气球(leetcode)
    https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/思路是排序,方便计算气球重叠,难点是在重叠时更新右边界,更新为两个区间的最右重合点,因为这个点是最少一支箭就可以射掉两个气球的最右点,再去下个循环判断区间重合classSolution{......
  • 【生日视频制作】公园火车飞艇热气球AE模板修改文字软件生成器教程特效素材【AE模板】
    公园火车飞艇热气球生日视频制作教程AE模板修改文字特效软件生成器素材怎么如何做的【生日视频制作】公园火车飞艇热气球AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:安装AE软件下载AE模板把AE模板导入AE软件修改图片或文字渲染出视频......
  • 【生日视频制作】充气热气球飞艇AE模板修改文字软件生成器教程特效素材【AE模板】
    热气球飞艇生日视频制作教程AE模板修改文字特效广软件告生成器【生日视频制作】充气热气球飞艇AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:安装AE软件下载AE模板把AE模板导入AE软件修改图片或文字渲染出视频......
  • 代码随想录day30 || 452 引爆气球,435 无重叠区间,763 划分字母区间
    452射爆气球funcfindMinArrowShots(points[][]int)int{ //思路,尝试按照startasc,endasc排序一下,取交集射爆 iflen(points)==1{ return1 } sort.Slice(points,func(i,jint)bool{ ifpoints[i][0]==points[j][0]{ returnpoints[i][1]<points......
  • 代码随想录算法训练营第二十六天|452. 用最少数量的箭引爆气球、435. 无重叠区间、763
    写代码的第二十六天继续贪心贪心!!!452.用最少数量的箭引爆气球思路最少的弓箭引爆气球,那么就是要看有没有重复覆盖的区域,如果有的话,那么一个弓箭就能引爆重复区域的气球,所以本题就是要看有多少气球是重复的,如果重复就用一根弓箭,如果不重复就加一。解决问题1:如何判断是否......
  • 两个燃点,引爆在线教育平台数智化
    关注字节跳动数据平台公众号,回复“火花思维”,获取高清方案设计及产品资料 2017年,专注于少儿逻辑思维的在线教育品牌火花思维正式成立,依托小班直播课、真人互动AI课等形式,火花思维将老师的启发引导和动画、游戏、趣味教具等载体结合,层层引导培养孩子的逻辑推理和问题解决能力......
  • Centos7下安装配置最新版本Jenkins(2.452.3)
    1、基础环境配置1.1服务器下载Jenkins安装包下载地址:https://www.jenkins.io/download/下载命令:wgethttps://get.jenkins.io/war-stable/2.452.3/jenkins.war1.2服务器安装配置JDKJenkins是基于Java语言开发的,因此需要Java运行环境支持。安装JDK前一定要看下当前要......
  • 2101. 引爆最多的炸弹 Medium
    给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。炸弹用一个下标从 0 开始的二维整数数组 bombs 表示,其中 bombs[i]=[xi,yi,ri] 。xi 和 yi 表示第 i 个炸弹的X和Y坐标,ri 表示爆炸范围的 半径 。你需要选择引爆 一个 炸弹。当......
  • 代码随想录算法训练营第33天 | 贪心4:452. 用最少数量的箭引爆气球、435. 无重叠区间
    代码随想录算法训练营第33天|贪心4:452.用最少数量的箭引爆气球、435.无重叠区间、763.划分字母区间452.用最少数量的箭引爆气球https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/代码随想录https://programmercarl.com/0452.用最......
  • 代码随想录day 31 用最少数量的箭引爆气球 | 无重叠区间 | 划分字母区间
    用最少数量的箭引爆气球用最少数量的箭引爆气球解题思路先根据数组中的第一个参数进行排序,之后通过记录最小右区间来判断是否重叠或者进入下个重叠区。贪心的思想是有重叠就尽可能地进行重叠,从而达到局部最优知识点重叠区间,贪心心得学会了如何判断和找寻重叠区间的方法无......