【算法刷题 | 贪心算法07】4.29(用最少数量的箭引爆气球、无重叠区间)

在这里插入图片描述

文章目录

  • 12.用最少数量的箭引爆气球
    • 12.1题目
    • 12.2解法:贪心
      • 12.2.1贪心思路
      • 12.2.2代码实现
  • 13.无重叠区间
    • 13.1题目
    • 13.2解法:贪心
      • 13.2.1贪心思路
      • 13.2.2代码实现

12.用最少数量的箭引爆气球

12.1题目

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

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

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

  • 示例一:
输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8]和[1,6]。
-在x = 11处发射箭,击破气球[10,16]和[7,12]。
  • 示例二:
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
  • 示例三:
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2]和[2,3]。
- 在x = 4处射出箭,击破气球[3,4]和[4,5]。

12.2解法:贪心

12.2.1贪心思路

image-20240429104021561

12.2.2代码实现

	public int findMinArrowShots(int[][] points) {
        //1、按照起始元素排序
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        int count=1;
        //2、从第二个元素开始遍历
        for(int i=1;i<points.length;i++){
            if(points[i][0]<=points[i-1][1]){
                //有重叠,更新重叠气球的最小右边界
                points[i][1]=Math.min(points[i][1],points[i-1][1]);
            }else{
                //没有重叠
                count++;
            }
        }
        return count;
    }

13.无重叠区间

13.1题目

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠

  • 示例一:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
  • 示例二:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
  • 示例三:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

13.2解法:贪心

13.2.1贪心思路

  • 将数组按照起始元素排序;
  • 从第二个元素开始遍历,判断该区间和上一个区间是否有重叠
    • 有重叠,则更新重叠区间的最小右边界,并count++,表示需要去掉该区间;

13.2.2代码实现

	public int eraseOverlapIntervals(int[][] intervals) {
        //1、按照起始元素排序
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int count=0;
        //2、从第二个元素开始遍历
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<intervals[i-1][1]){
                //有重叠,更新重叠气球的最小右边界
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
                count++;
            }else{
                //没有重叠
                
            }
        }
        return count;
    }

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Kafka 3.x.x 入门到精通(08)——对标尚硅谷Kafka教程

Kafka 3.x.x 入门到精通&#xff08;08&#xff09;——对标尚硅谷Kafka教程 5. Kafka优化5.1 资源配置5.1.1 操作系统5.1.2 磁盘选择5.1.3 网络带宽5.1.4 内存配置5.1.5 CPU选择 5.2 集群容错5.2.1 副本分配策略5.2.2 故障转移方案5.2.3 数据备份与恢复 5.3 参数配置优化5.4 数…

如何在WordPress中设置网站的SEO标题和描述

在WordPress中&#xff0c;想要让你的网站在搜索引擎结果中脱颖而出&#xff0c;设置优秀的SEO标题和描述至关重要。这不仅可以帮助搜索引擎更好地理解你的网站内容&#xff0c;还可以吸引更多的点击率和流量。而选择一款合适的SEO插件是实现这一目标的关键之一。让我们来看看两…

电路邱关源学习笔记——3.6结点电压法

1.结点电压法 以结点电压为未知量列写电路方程分析电路的方法。适用于结点较少的电路。 基本思想 选取结点电压为未知量&#xff0c;则KVL自动满足&#xff0c;无需列写KVL方程。各支路电流、电压可视为结点电压的线性组合。求出结点电压之后&#xff0c;便可方便地得到各支路…

怎样批量将jpg图片转换成HEIC格式?jpg快速转换成HEIC图片

heic格式和jpg格式图片大家都很熟悉了。那么这两种图片格式的区别是什么&#xff1f;哪种格式图片更好一些&#xff1f; 一&#xff0c;区别&#xff1a;jpg和HEIC的区别 1&#xff0c;jpg格式有良好的压缩性能和良好的重建质量而被广泛应用于图像和视频处理中。 2&#xff…

代码随想录刷题随记29-贪心3

代码随想录刷题随记29-贪心3 1005.K次取反后最大化的数组和 leetcode链接 比较简单&#xff0c;首先对数组进行绝对值排序&#xff0c;然后如果是负数从小到大进行反转 如果是正数&#xff0c;就对一个绝对值最小的一直翻转 按照绝对值排序的实现可以通过重写比较器实现 cla…

ComfyUI-AniPortrait——数字人插件

仓库地址&#xff1a;GitHub - chaojie/ComfyUI-AniPortrait 往期学习资料 整理AI学习资料库 需要的模型如下 工作流如下&#xff1a; 首先把上面的sd-vae-ft-mse、wav2vec2-base-960h模型放到下面的目录&#xff0c;如下 其他模型放到哪里都行&#xff0c;反正是自定义模型…

ThreeJs模拟工厂生产过程八

这节算是给这个车间场景收个尾&#xff0c;等了几天并没有人发设备模型给我&#xff0c;只能自己找了一个凑合用了。加载模型之前&#xff0c;首先要把货架上的料箱合并&#xff0c;以防加载模型之后因模型数量多出现卡顿&#xff0c;方法和之前介绍的合并传送带方法相同&#…

uniapp视频播放器(h5+app)

关于uniapp视频播放器遇到的一些问题&#xff0c;mark下。 中途遇到了很多问题&#xff0c;如果有相同的伙伴遇到了类似的&#xff0c;欢迎交流 官方的video播放器在app上不友好&#xff0c;有以下功能不支持。 loadedmetadata、controlstoggle不支持导致只能手写控制层。 不…

集成框架 -- OSS

前言 接入oss必须有这两个文档基础 使用STS临时访问凭证访问OSS_对象存储(OSS)-阿里云帮助中心 前端上传跨域 正文 sts前后端通用&#xff0c;开通图示 AliyunSTSAssumeRoleAccess 后端实现代码 public static void main(String[] args) {String regionId "cn-ha…

Oracle 表分区

1.概述 分区表就是将表在物理存储层面分成多个小的片段&#xff0c;这些片段即称为分区&#xff0c;每个分区保存表的一部分数据&#xff0c;表的分区对上层应用是完全透明的&#xff0c;从应用的角度来看&#xff0c;表在逻辑上依然是一个整体。 目的&#xff1a;提高大表的查…

2024年北京市中小学生信息学能力测评活动BCSP-X小学低年级组初赛测试题(模拟题)

一、单项选择&#xff08;共 15 题&#xff0c;每题 2 分&#xff0c;共计 30 分&#xff0c;每题有且仅有一个正确选项&#xff09; 不可以作为c中的变量名的是&#xff08; &#xff09;。 A. I以下loveChinaB. I_loveChinaC. I_love_ChinaD. i_loveChina 在体育课上&#xf…

teamOS协作通知,我的新晋办公搭子,完美把控项目动态,再也不担心错过协作变更了,谁也不能背着我偷偷内卷

有没有碰到过这样的情况&#xff0c;在企业网盘中建了新项目的协作组&#xff0c;和团队成员一起做项目&#xff0c;正常来说应该是能更好的完成工作。 但是现实就是&#xff0c;项目文件修改了&#xff0c;如果不用微信或者其他方式发个通知&#xff0c;团队成员往往都不知道…

selenium 4.x 入门(环境搭建、八大元素定位)

背景 Web自动化测现状 1. 属于 E2E 测试 2. 过去通过点点点 3. 好的测试&#xff0c;还需要记录、调试网页的细节 一、selenium4.x环境搭建 一键搭建 pip3 install webdriver-helper 有建议要 1.0.1 版本的&#xff0c;但本人按上面的是可以正常使用&#xff08;看…

计算机科学与技术就业方向和前景怎么样

计算机科学与技术专业的就业方向极为广泛&#xff0c;方向可以是软件开发与工程、网络与信息安全、数据科学与大数据分析等&#xff0c;几乎渗透到现代社会的每一个角落。以下是上大学网 &#xff08;www.sdaxue.com)对计算机科学与技术专业一些主要的就业方向及其前景分析&…

【Redis 开发】Redis哨兵

哨兵 作用和原理服务状态监控选举新的master 搭建哨兵集群RedisTemplate的哨兵模式 作用和原理 Redis提供了哨兵机制来实现主从集群中的自动故障恢复&#xff1a; 哨兵也是一个集群 监控&#xff1a;会不断检查master和slave是否按预期工作自动故障恢复&#xff1a;如果mast…

基于FPGA的数字信号处理(2)--什么是定点数?

在实际的工程应用中&#xff0c;往往会进行大量的数学运算。运算时除了会用到整数&#xff0c;很多时候也会用到小数。而我们知道在数字电路底层&#xff0c;只有「高电平1」和「低电平0」的存在&#xff0c;那么仅凭 0和1 该如何表示小数呢&#xff1f; 数字电路中&#xff0…

SpringBoot实现图片上传(个人头像的修改)

SpringBootlayui实现个人信息头像的更改 该文章适合对SpringBoot&#xff0c;Thymeleaf&#xff0c;layui入门的小伙伴 废话不多说&#xff0c;直接上干货 Springbootlayui实现头像更换 前端公共部分代码 HTML页面代码 <div class"layui-card-header" style&quo…

IP定位技术企业网络安全检测

随着信息技术的飞速发展&#xff0c;网络安全问题日益凸显&#xff0c;成为企业运营中不可忽视的一环。在众多网络安全技术中&#xff0c;IP定位技术以其独特的优势&#xff0c;为企业网络安全检测提供了强有力的支持。本文将深入探讨IP定位技术在企业网络安全检测中的应用及其…

QT学习之读取xml中信息

背景&#xff1a; 我们每次注册后会生成对应的启动码文件&#xff0c;格式如下&#xff0c;启动码最后要在测试工具使用的进行一个验证&#xff0c;验证通过后模块才能使用。所以我希望每次的xml都放在一个文件夹里&#xff0c;等我选择文件夹后&#xff0c;能提取所有xml中的对…

手把手教会西门子PLC代码可视化功能——Prodiag

一、传统的HMI报警方法 在HMI中建立离散量报警&#xff0c;输入报警文本。这种方法的劣势&#xff1a; 1、在PLC程序中需要建立专门报警程序&#xff0c;用于关联HMI中的报警变量 2、需要在HMI文本中输入报警文本 如果程序复杂&#xff0c;报警众多&#xff0c;用这种方法需…