[leetcode hot 150]第四百五十二题,用最少数量的箭引爆气球

题目:

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstartxend, 且满足  xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 

 

 解决这个问题的关键是要找到尽可能多的重叠区间。可以使用贪心算法:

  1. 首先,按照气球的结束坐标(xend)对所有气球进行排序。
  2. 然后,从第一个气球开始,射出一支箭。
  3. 看这支箭能否引爆下一个气球,如果能,继续看下一个。
  4. 如果不能,就需要再射出一支箭。
import java.util.Arrays;
import java.util.Comparator;public class no_452 {public static void main(String[] args) {int[][] quJian = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};System.out.println(findMinArrowShots(quJian));}public static int findMinArrowShots(int[][] points) {if (points == null || points.length == 0) return 0;Arrays.sort(points, Comparator.comparingInt(a -> a[1]));int arrowPos = points[0][1];int arrowCount = 1;for (int i = 1; i < points.length; i++) {if (points[i][0] > arrowPos) {arrowCount++;arrowPos = points[i][1];}}return arrowCount;}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/367756.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《昇思25天学习打卡营第6天 | 函数式自动微分》

《昇思25天学习打卡营第6天 | 函数式自动微分》 目录 《昇思25天学习打卡营第6天 | 函数式自动微分》函数式自动微分简单的单层线性变换模型函数与计算图微分函数与梯度计算Stop Gradient 函数式自动微分 神经网络的训练主要使用反向传播算法&#xff0c;模型预测值&#xff0…

JAVA每日作业day7.1-7.3小总结

ok了家人们前几天学了一些知识&#xff0c;接下来一起看看吧 一.API Java 的 API &#xff08; API: Application( 应用 ) Programming( 程序 ) Interface(接口 ) &#xff09; Java API 就是 JDK 中提供给我们使用的类&#xff0c;这些类将底层 的代码实现封装了起来&#x…

Linux多进程和多线程(四)进程间通讯-定时器信号和子进程退出信号

多进程(四) 定时器信号alarm()函数示例alarm()函数的限制定时器信号的实现原理setitimer()函数setitimer()和alarm()函数的区别 setitimer() old_value参数的示例 对比alarm()区别总结&#xff1a; 子进程退出信号 示例: 多进程(四) 定时器信号 SIGALRM 信号是用来通知进程…

新声创新20年:无线技术给助听器插上“娱乐”的翅膀

听力损失并非现代人的专利&#xff0c;古代人也会有听力损失。助听器距今发展已经有二百多年了&#xff0c;从当初单纯的声音放大器到如今的全数字时代助听器&#xff0c;助听器发生了翻天覆地的变化&#xff0c;现代助听器除了助听功能&#xff0c;还具有看电视&#xff0c;听…

微信小程序 调色板

注意&#xff1a;是在uniapp中直接使用的一个color-picker插件&#xff0c;改一下格式即可在微信小程序的原生代码中使用 https://github.com/KirisakiAria/we-color-picker 这是插件的地址&#xff0c;使用的话先把这个插件下载下来&#xff0c;找到src&#xff0c;在项目创…

FreeRTOS和UCOS操作系统使用笔记

FreeRTOS使用示例 UCOS使用示例 信号量使用 信号量访问共享资源区/ OS_SEMMY_SEM; //定义一个信号量&#xff0c;用于访问共享资源OSSemCreate ((OS_SEM* )&MY_SEM, //创建信号量&#xff0c;指向信号量(CPU_CHAR* )"MY_SEM", //信号量名字(OS_SEM_CTR )1, …

imx6ull/linux应用编程学习(8)PWM应用编程(基于正点)

1.应用层如何操控PWM&#xff1a; 与 LED 设备一样&#xff0c; PWM 同样也是通过 sysfs 方式进行操控&#xff0c;进入到/sys/class/pwm 目录下 这里列举出了 8 个以 pwmchipX&#xff08;X 表示数字 0~7&#xff09;命名的文件夹&#xff0c;这八个文件夹其实就对应了…

守护矿山安全生产:AI视频分析技术在煤矿领域的应用

随着人工智能&#xff08;AI&#xff09;技术的快速发展&#xff0c;其在煤矿行业的应用也日益广泛。AI视频智能分析技术作为其中的重要分支&#xff0c;为煤矿的安全生产、过程监测、效率提升和监管决策等提供了有力支持。 一、煤矿AI视频智能分析技术的概述 视频智慧煤矿AI…

数据库测试数据准备厂商 Snaplet 宣布停止运营

上周刚获知「数据库调优厂商 OtterTune 宣布停止运营」。而今天下班前&#xff0c;同事又突然刷到另一家海外数据库工具商 Snaplet 也停止运营了。Snaplet 主要帮助开发团队在数据库中生成仿真度高且合规的测试数据。我们在年初还撰文介绍过它「告别手搓&#xff01;Postgres 一…

Continual Test-Time Domain Adaptation--论文笔记

论文笔记 资料 1.代码地址 https://github.com/qinenergy/cotta 2.论文地址 https://arxiv.org/abs/2203.13591 3.数据集地址 论文摘要的翻译 TTA的目的是在不使用任何源数据的情况下&#xff0c;将源预先训练的模型适应到目标域。现有的工作主要考虑目标域是静态的情况…

Vue项目打包上线

Nginx 是一个高性能的开源HTTP和反向代理服务器&#xff0c;也是一个IMAP/POP3/SMTP代理服务器。它在设计上旨在处理高并发的请求&#xff0c;是一个轻量级、高效能的Web服务器和反向代理服务器&#xff0c;广泛用于提供静态资源、负载均衡、反向代理等功能。 1、下载nginx 2、…

探讨命令模式及其应用

目录 命令模式命令模式结构命令模式适用场景命令模式优缺点练手题目题目描述输入描述输出描述题解 命令模式 命令模式是一种行为设计模式&#xff0c; 它可将请求转换为一个包含与请求相关的所有信息的独立对象。 该转换让你能根据不同的请求将方法参数化、 延迟请求执行或将其…

【高级篇】第9章 Elasticsearch 监控与故障排查

9.1 引言 在现代数据驱动的应用架构中,Elasticsearch不仅是海量数据索引和搜索的核心,其稳定性和性能直接影响到整个业务链路的健康度。因此,建立有效的监控体系和掌握故障排查技能是每一位Elasticsearch高级专家的必备能力。 9.2 监控工具:洞察与优化的利器 在Elastics…

Rough.js在Vue3中生成随机蒙德里安风格的抽象艺术

本文由ScriptEcho平台提供技术支持 项目地址&#xff1a;传送门 Mondrian风格艺术生成器&#xff1a;用Vue和RoughJS创造抽象艺术 应用场景 Mondrian风格艺术以其大胆的色彩块和简单的几何形状而闻名。这种风格可以应用于各种设计项目&#xff0c;包括海报、插图和网页设计…

基于Web技术的教育辅助系统设计与实现(SpringBoot MySQL)+文档

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…

Markdown+VSCODE实现最完美流畅写作体验

​下载VSCODE软件 安装插件 Markdown All in One &#xff1a;支持markdown的语言的&#xff1b; Markdown Preview Enhanced &#xff1a;观看写出来文档的效果&#xff1b; Paste IMage :添加图片的 Code Spell Checker检查英文单词错误&#xff1b; 基础语法 标题 #一个…

AI 会淘汰程序员吗?

前言 前些日子看过一篇文章&#xff0c;说国外一位拥有 19 年编码经验、会 100% 手写代码的程序员被企业解雇了&#xff0c;因为他的竞争对手&#xff0c;一位仅有 4 年经验、却善于使用 Copilot、GPT-4 的后辈&#xff0c;生产力比他更高&#xff0c;成本比他更低&#xff0c…

西南交通大学【算法分析与设计实验3】

实验3.3 任务分配问题 实验目的 &#xff08;1&#xff09;理解穷举法典型算法的求解过程。 &#xff08;2&#xff09;学习穷举法的时间复杂度分析方法&#xff0c;并通过实验验证算法的执行效率。 &#xff08;3&#xff09;学会如何利用穷举法求解具体问题&#xff0c;了…

按是否手工执行测试的角度划分:手工测试、自动化测试

1.手工测试&#xff08;Manual testing&#xff09; 手工测试是由人一个一个的输入用例&#xff0c;然后观察结果&#xff0c;和机器测试相对应&#xff0c;属于比较原始但是必须的一个步骤。 由专门的测试人员从用户视角来验证软件是否满足设计要求的行为。 更适用针对深度…

哈希表 | 哈希查找 | 哈希函数 | 数据结构 | 大话数据结构 | Java

&#x1f64b;大家好&#xff01;我是毛毛张! &#x1f308;个人首页&#xff1a; 神马都会亿点点的毛毛张 &#x1f4cc;毛毛张今天分享的内容&#x1f586;是数据结构中的哈希表&#xff0c;毛毛张主要是依据《大话数据结构&#x1f4d6;》的内容来进行整理&#xff0c;不…