本文主要是介绍力扣452-用最少数量的箭引爆气球(Java详细题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:452. 用最少数量的箭引爆气球 - 力扣(LeetCode)
前情提要:
因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。
贪心方法:局部最优推出全局最优。
如果一个题你觉得可以用局部最优推出全局最优,并且没有反例来反驳的话就可以用贪心来试试。
题目思路:
其实本题模拟一遍后思路不难想,就是尽可能的找重叠的区域,一箭可以把重叠的全射了。
全局最优:用最小的弓箭数就能射完。
首先对数组排序 这样才会尽可能的重叠。
那怎么寻找重叠的区域呢?
重叠区域的方式有很多种,我们可以先处理不重叠的部分。
只要当前的左边界大于上一个气球右边界,那么这俩气球肯定不重叠。
只要不重叠,我就要开始增加我的弓箭数了。
那么不重叠的区域考虑完后,我们是不是就要考虑重叠的区域。
其实在代码里很好考虑重叠的部分,只要if else就好啦。
if判断不重叠,那么else的就是重叠的部分了。
我们判断当前气球与上一个气球重叠时,我们还应该判断与下一个气球是否重叠。
如果重叠,那就一箭就可以了。
不重叠,就要再加一箭了。
如何判断是否与下一个重叠呢?
其实我们只要将本层的右边界与上一个的右边界取最小值。
这样遍历到下一层时,他与上一层的右边界进行比较,就能知道本层能不能与上俩层一起重叠。
举个例子。
ok 思路大概就是这样。 我们来看最终代码吧。
class Solution {public int findMinArrowShots(int[][] points) {//这里需要特判一下 当数组数量为0时 气球都为0了 那我就不用射箭了 所以直接返回0if(points.length == 0)return 0;//注意这里初始化为1 因为只要数组数量大于0,就肯定需要一支箭 就当第一只箭已经处理了 后面一旦出现不重叠的部分肯定就需要俩支箭int result = 1;Arrays.sort(points,(a,b) -> Integer.compare(a[0], b[0]));for(int i = 1;i < points.length;i ++){//只要当前的大于上一个 那么本层就直接射 射箭数就加一 //也就是出现了不重叠的部分 我肯定是要用俩箭才能射掉 也就是加了一箭if(points[i][0] > points[i - 1][1]){result ++;}else{//当前这层右边界就等于与上一层比较的最小值//这样就能判断上两层与下一层是否重叠points[i][1] = Math.min(points[i][1],points[i - 1][1]);}}return result;}
}
其实代码并不复杂,思路也不难想,大家多模拟几遍就好。
这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。
我很乐意为你解答。那么我们下篇再见!
这篇关于力扣452-用最少数量的箭引爆气球(Java详细题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!