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

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

时间:2023-05-08 17:13:03浏览次数:36  
标签:return 452 points 坐标 弓箭 引爆 气球

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

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

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

示例 1:

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

标准解法

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

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,注意这里不是>=
                result++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
            }
        }
        return result;
    }
};

标签:return,452,points,坐标,弓箭,引爆,气球
From: https://www.cnblogs.com/lihaoxiang/p/17382344.html

相关文章

  • NC14522 珂朵莉的数列
    题目链接题目题目描述珂朵莉给了你一个序列,有\(\frac{n\times(n+1)}2\)个子区间,求出她们各自的逆序对个数,然后加起来输出输入描述第一行一个数n表示这个序列a的长度之后一行n个数,第i个数表示ai输出描述输出一行一个数表示答案示例1输入1011085623947......
  • 大模型带来算力巨量需求,有望引爆AI服务器市场
    随着数字化转型需求增长,AI在企业中的应用也越来越多,AI开发门槛高、应用场景复杂多样、对场景标注数据依赖等问题成为AI规模化落地的挑战,而预训练大模型的出现则为人工智能带来了新的机遇与希望。大模型作为政府和企业推进人工智能产业发展的重要抓手,在识别、理解、决策、生成等AI任......
  • day35| 860+406+452
    860.柠檬水找零 题目简述:在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单bills支付的顺序)一次购买一杯。每位顾客只买一杯柠檬水,然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付5美元。注意......
  • 【DP】LeetCode 312. 戳气球
    题目链接312.戳气球思路参考动态规划套路解决戳气球问题分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律在数组的动态规划问题中,一般dp[i]都是表示以nums[i]为结尾的状态;dp[i][j]分别表示以nums1[i]和nums......
  • HDU 1452 Happy 2004 (积性函数)
    题目地址:HDU1452性质1:如果gcd(a,b)=1则S(a*b)=S(a)*S(b)2004^X=4^X*3^X*167^XS(2004^X)=S(2^(2X))*S(3^X)*S(167^X)性质2:如果p是素数则S(p^X)=1+p+p^2+…+p^X=(p^(X+1)-1)/(p-1)因此:S(2004^X)=(2^(2X+1)-1)*(3^(X+1)-1)/2*(167^(X+1)-1)/166......
  • 算法随想Day31【贪心算法】| LC860-柠檬水找零、LC406-根据身高重建队列、LC452-用最
    LC860.柠檬水找零boollemonadeChange(vector<int>&bills){intC5=0,C10=0;for(inti=0;i<bills.size();++i){if(bills[i]==5......
  • 线段树维护哈希 | CF213E Two Permutations + CF452F Permutation
    __终于学到了线段树维护xx,嘿嘿,嘿嘿嘿..树树:D做了两题,感觉知识点是维护区间相同不相同可以拿hash做,不连续的区间也可以拿hash维护主要是出得很有想法,太妙了要想得到hh1.......
  • ChatGPT引爆AIGC,垂类龙头迎来“创新春天”
    文|智能相对论作者|陈壹一款AI产品,到底有多神?ChatGPT刷新了我们的认知。它用2个月时间,完成TikTok花9个月,Instagram花2年半才做到的事,成为史上用户增速最快破亿的消费级应用......
  • 312. 戳气球 (Hard)
    问题描述312.戳气球(Hard)有n个气球,编号为0到n-1,每个气球上都标有一个数字,这些数字存在数组nums中。现在要求你戳破所有的气球。戳破第i个气球,你可以获得......
  • 刷刷刷 Day 35 | 452. 用最少数量的箭引爆气球
    452.用最少数量的箭引爆气球LeetCode题目要求有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i]=[xstart,xend] ......