LeetCode 题解:452. Minimum Number of Arrows to Burst Balloons

2024-03-31 16:38

本文主要是介绍LeetCode 题解:452. Minimum Number of Arrows to Burst Balloons,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:
Input:
[[10,16], [2,8], [1,6], [7,12]]Output:
2

解题思路

这道题的解决思路其实就是找重叠区间最多的位置x的数量。此题采用贪心算法求解。算法共三步:

1、将存储气球位置的points数组按照每个气球的起始点的位置进行排序,便于后续操作。这里使用系统内置的sort函数。

2、设定初始可以放置箭矢发射的位置空间为0号气球的位置(排序后的points数组的0号元素points[0]),放置箭矢发射的位置空间的右边界用变量 end 记录。

3、假如第x个气球的左边界小于当前记录的 end 值,说明当前放置的箭矢可以射爆第x个气球,箭矢的数量不需要增加。但要注意,第x个气球的右边界可能小于当前记录的 end 值,此时需要将当前的重叠区域的右边界更新为第x个气球的右边界。否则,假如第x个气球的左边界已经大于当前记录的 end 值,那说明这个气球不能被射爆,要使用新的箭矢。箭矢的数量要加1,同时将 end 值更新为第x个气球的右边界。重复上述步骤直到遍历完所有气球。

注:由于points数组已经按照每个气球的左边界进行了排序,因此后面的算法过程不再需要记录气球的左边界的位置,因为从位置 end 射出的箭矢一定能射爆重叠区域的所有气球。

C++代码

class Solution {
public:int findMinArrowShots(vector<pair<int, int>>& points) {if(points.empty()) return 0;sort(points.begin(), points.end(), [](const pair<int, int> a, const pair<int, int> b){ return a.first < b.first; });int arrows = 1;int end = points[0].second;for(int i = 1; i < points.size(); i++) {if(points[i].first <= end) {if(end >= points[i].second)end = points[i].second;}else {arrows++;end = points[i].second;}}return arrows;}
};

这篇关于LeetCode 题解:452. Minimum Number of Arrows to Burst Balloons的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/864805

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样