力扣452-用最少数量的箭引爆气球(Java详细题解)

2024-09-01 14:28

本文主要是介绍力扣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详细题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,:本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大?如何处理这个文件?分析文件内容(推荐)删除文件(如果不需要)查看错误来源如何避

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

SpringBoot整合Dubbo+ZK注册失败的坑及解决

《SpringBoot整合Dubbo+ZK注册失败的坑及解决》使用Dubbo框架时,需在公共pom添加依赖,启动类加@EnableDubbo,实现类用@DubboService替代@Service,配... 目录1.先看下公共的pom(maven创建的pom工程)2.启动类上加@EnableDubbo3.实

SpringBoot整合(ES)ElasticSearch7.8实践

《SpringBoot整合(ES)ElasticSearch7.8实践》本文详细介绍了SpringBoot整合ElasticSearch7.8的教程,涵盖依赖添加、客户端初始化、索引创建与获取、批量插... 目录SpringBoot整合ElasticSearch7.8添加依赖初始化创建SpringBoot项

JAVA覆盖和重写的区别及说明

《JAVA覆盖和重写的区别及说明》非静态方法的覆盖即重写,具有多态性;静态方法无法被覆盖,但可被重写(仅通过类名调用),二者区别在于绑定时机与引用类型关联性... 目录Java覆盖和重写的区别经常听到两种话认真读完上面两份代码JAVA覆盖和重写的区别经常听到两种话1.覆盖=重写。2.静态方法可andro

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs