用最少数量的箭引爆气球 Posted on 2021-08-16 00:00:00 2021-08-16 00:00:00 by Author 摘要 给一排相互之间有重叠的气球,你能用最少的弓箭去引爆这些气球吗???? ## 用最少数量的箭引爆气球 1. 题目描述 - 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。 - **提示：** - 0 <= points.length <= 10^4 - points[i].length == 2 - -2^31 <= xstart < xend <= 2^31 - 1 2. 示例描述 - 示例一 ```java 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球 ``` - 示例二 ```java 输入：points = [[2,3],[2,3]] 输出：1 ``` - 示例三 ```java 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 ``` 3. 解题思路 - 首先拿到这道题之后，说实话理解题目我都理解了不下三遍，因为读完题目的时候，被自己的想法卡住了，当时想的是大气球里面还能装小气球吗，那么这道题是不是为了出题而出题啊。之后读了多遍后发现自己理解错了，假如气球有重叠的部分，后一个气球可以放在前一个气球的后面(有重叠的部分被前一个气球挡住了)其余的部分还是能在水平方向上看到的。 - 理解题目之后，其实思想很简单就是找到多个气球的重叠点，然后这多个气球的引爆就只需要一只箭，从而消耗更少的箭。其实想法很简单，但是怎么实现尼？ - 这道题最主要的难度就是怎么找到气球的重叠点（尽可能找到更多的气球的重叠点），首先题目给定的数组(气球起始位置坐标)都是乱序的，所以在进行处理前需要对数组进行排序(即第一维度,气球的开始位置)排完序之后就能更好的找到气球的重叠点。 那么气球的重叠点应该怎么判断尼，即前一个气球的终点大于或者等于后一个气球的起始点，那么说明相邻的两个气球有重叠，然鹅重叠点找到了，这只是找到两个气球的重叠点，假如之后的气球和前两个气球有重叠点，那怎么办呢？那就需要一直找到没有重叠的部分为止，这样才能消耗更少的箭射更多的气球。 - 那怎么找到多个气球的重叠点尼。我们可以从每个相邻的两个两个气球进行考虑，如果相邻的两个气球有重叠，那么后一个气球记住重叠部分的起始于结束为止，那么后一个气球怎么记住重叠的部分尼，首先我们晓得如果相邻的气球有重叠，那么后一个气球的开始位置一定在重叠的区间里，那么重叠的终点位置就是前一个气球终点位置与后一个气球终点位置的最小值(最小值哦，这里应该都想的通吧！),那么本次相邻的气球重叠位置记录在后一个气球数组了，在遇到下一个气球，继续比较已经计算过了的重叠位置是否与接下来气球有重叠的地方，如果有重叠就继续更新重叠点，如果没有那就需要消耗一只弓箭了。直到遍历完整个数组后，就能找到需要消耗最少的弓箭数量了。 - 这道题是有贪心思想在里面的，当气球出现重叠，一起射，所用弓箭最少。这是局部最优解，那么把所有气球射爆所用弓箭最少，就得到全局最优解。 - 以下就是代码示例，如果可以手动实现一遍，我相信会更加理解下面的代码了。 4. 代码示例 ```java public int findMinArrowShots(int[][] points) { //首先对所有的气球从开始位置进行从小到大排序 //即对数组第一维度进行从小到大排序 Arrays.sort(points,( p1, p2)->{ return p1[0] > p2[0]?1:-1; }); //如果给定的数组长度为0，说明没有气球，返回0(边界条件) if(points.length==0)return 0; //初始化用的箭为1(最少为一个，在气球个数不为0的情况下) int result=1; for(int i=1;i<points.length;i++){ //上个气球与这个气球没有重叠的部分，说明射爆这个气球需要消耗一只弓箭 if((long)(points[i-1][1])<((long)points[i][0])){ result++; } else{ //如果上个气球与这个气球有重叠的部分，那么射爆上个气球用的弓箭也可以射爆这个气球， //所有不需要消耗弓箭 //如果接下来还有别的气球与这气球有重叠，那么找到没有重叠气球位置，才能消耗下一只弓箭 points[i][1]=Math.min(points[i-1][1],points[i][1]); } } //返回最终结果 return result; } ```
{{ item.content }}
{{ child.content }}