贪心算法解决用最少数量的箭引爆气球问题

devtools/2025/1/1 22:38:11/

代码随想录链接:代码随想录

思路:

要想射出的弓箭最少,需要统计重叠的气球的数量,如果多个气球重叠的话使用一支箭即可

首先对数组中每个子数组进行排序,排序的规则是它们的第一个元素从小到大的顺序

从第一个子数组开始遍历数组中的全部子数组,如果当前遍历的第i个子数组的第0个元素大于第i-1个子数组的第1个元素,那么表示这两气球不重叠,此时统计弓箭的变量+1

否则表示这两个气球重叠,此时更新第i个子数组的第1个元素,更新的值为第i个子数组的第1个元素第i-1个子数组的第1个元素中较小值

对应Java代码:

class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序// 使用Integer内置比较方法,不会溢出Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int count = 1;  // points 不为空至少需要一支箭for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,注意这里不是>=count++; // 需要一支箭} else {  // 气球i和气球i-1挨着points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界}}return count;}
}


http://www.ppmy.cn/devtools/145163.html

相关文章

IntelliJ IDEA中设置激活的profile

在IntelliJ IDEA中设置激活的profile&#xff0c;可以通过以下步骤进行&#xff1a; 通过Run/Debug Configurations设置 打开Run/Debug Configurations对话框&#xff1a; 在IDEA的顶部菜单栏中&#xff0c;选择“Run”菜单&#xff0c;然后点击“Edit Configurations...”或者…

VSCode 搭建Python编程环境 2024新版图文安装教程(Python环境搭建+VSCode安装+运行测试+背景图设置)

名人说&#xff1a;一点浩然气&#xff0c;千里快哉风。—— 苏轼《水调歌头》 创作者&#xff1a;Code_流苏(CSDN) 目录 一、Python环境安装二、VScode下载及安装三、VSCode配置Python环境四、运行测试五、背景图设置 很高兴你打开了这篇博客&#xff0c;更多详细的安装教程&…

CTFHub disable_functions通过

LD_PRELOAD 来到首页发现有一句话直接就可以用蚁剑连接 根目录里有/flag但是不能看;命令也被ban了就需要绕过了 绕过工具在插件市场就可以下载 如果进不去的话 项目地址: #本地仓库;插件存放 antSword\antData\plugins 绕过选择 上传后我们点进去可以看到多了一个绕过的文件;…

MySQL基础篇-多表查询(隐式/显式内连接、左/右外连接、自连接查询、联合查询、标量/列/行/表子查询)

Hiヽ(゜▽゜ )&#xff0d;欢迎来到蓝染Aizen的CSDN博客~ &#x1f525; 博客主页&#xff1a; 【✨蓝染 の Blog&#x1f618;】 &#x1f496;感谢大家点赞&#x1f44d; 收藏⭐ 评论✍ 文章目录 MySQL基础篇-多表查询一、多表关系1. 一对多2. 多对多3. 一对一 二、多表查询…

C#—内建接口: IEnumerable与IEnumerator接口详解

IEnumerable接口 在C#中&#xff0c;IEnumerable 是一个泛型接口&#xff0c;它表示一个可以通过 IEnumerator 迭代器进行迭代枚举的集合。这个接口是非常基础且重要的&#xff0c;因为它允许开发者以一致的方式遍历任何实现了该接口的集合&#xff0c;无论是数组、列表、自定…

绩效考核试题

1.2.绩效考核 &#xff08;&#xff09;通过财务、客户、内部运营、学习与成长4个角度&#xff0c;将组织战略目标逐层分解转化为细化指标&#xff0c;有差异地针对不同的指标进行不同时期的绩效评估&#xff0c;有助于组织战略目标的实现。 A目标管理法 B平衡计分卡法 C硬性分…

VS Code Copilot 与 Cursor 对比

选手简介 VS Code Copilot&#xff1a;算是“老牌”编程助手了&#xff0c;虽然Copilot在别的编辑器上也有扩展&#xff0c;不过体验最好的还是VS Code&#xff0c;毕竟都是微软家的所以功能集成更好一些&#xff1b;主要提供的是Complete和Chat能力&#xff0c;也就是代码补全…

Tool之Excalidraw:Excalidraw(开源的虚拟手绘风格白板)的简介、安装和使用方法、艾米莉应用之详细攻略

Tool之Excalidraw&#xff1a;Excalidraw(开源的虚拟手绘风格白板)的简介、安装和使用方法、艾米莉应用之详细攻略 目录 Excalidraw 简介 1、Excalidraw 的主要特点&#xff1a; Excalidraw 安装和使用方法 1、Excalidraw的安装 T1、使用 npm 安装&#xff1a; T2、使用 …