力扣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

相关文章

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断

java如何解压zip压缩包

《java如何解压zip压缩包》:本文主要介绍java如何解压zip压缩包问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解压zip压缩包实例代码结果如下总结java解压zip压缩包坐在旁边的小伙伴问我怎么用 java 将服务器上的压缩文件解压出来,

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

Spring事务传播机制最佳实践

《Spring事务传播机制最佳实践》Spring的事务传播机制为我们提供了优雅的解决方案,本文将带您深入理解这一机制,掌握不同场景下的最佳实践,感兴趣的朋友一起看看吧... 目录1. 什么是事务传播行为2. Spring支持的七种事务传播行为2.1 REQUIRED(默认)2.2 SUPPORTS2