贪心算法关键点加力扣452用最少数量的箭引爆气球解析

news/2024/7/19 15:51:08 标签: 贪心算法, 算法, js

1.当遇到多个条件需要考虑的时候,一定、一定、一定要先考虑其中一个条件,然后再考虑下一个条件,否则很容易两边都顾不上。

2.不论时刷题还是面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心,软件不想硬件,软件没有试错成本,想到了就可以去干,即使错了也就是找到了一种不适合这道题的方法,数学推导并不在我们需要考虑的范围内。

力扣452用最少数量的箭引爆气球解析:

题目的意思可以理解为:在x轴正方向与y轴正方向之间的区间内有一定数量的气球,从x轴某一点沿y轴方向射出一支箭,如果该箭射出位置在气球所在范围内则可以引爆该气球,求最少使用的箭数。(气球y坐标不知道,意思是气球在y轴方向是可以重叠的)

思路:使用最少的箭数,就是每箭引爆相对更多的气球,为什么不是绝对更多的呢,因为如果按照绝对更多,那么假设总共有6个气球,中间重叠区域有4个气球,左边重叠三个,右边重叠三个,如果先射中间,那么需要3箭,如果左右各射一箭,那么只需要两箭。

解析:将气球的初始位置按照从小到大的顺序排序,设左端点l为第一个气球的开始位置,右端点r为第一个气球结束位置,在l与r组成的区间内是必须射一箭的。设使用箭数res初始为1,从第二个气球开始遍历,判断左端点是否在l和r组成的区间内,如果在,那么左区间取原来的l值和当前遍历气球的左端点的最大值,右区间取原来r值和当前遍历起球右端点的最小值;如果不在,那么l等于当前气球开始点,r等于当前气球结束点,使用箭数res加一。

附代码:

        var findMinArrowShots = function (points) {
            points.sort((a, b) => a[0] - b[0])//将气球按照初始位置排序,不考虑结束位置
            let res = 1, l = points[0][0], r = points[0][1]
            for (let i = 1; i < points.length; i++) {
                if (points[i][0] <= r && points[i][0] >= l) {//如果本气球开始位置在区间内,那么就重新取最小区间,
                    l = Math.max(l, points[i][0])
                    r = Math.min(r, points[i][1])
                } else {//如果本气球不在区间里,让左右区间变成本气球所在区间,使用箭数加一
                    res++
                    l = points[i][0]
                    r = points[i][1]
                }
            }
            return res
        };

http://www.niftyadmin.cn/n/5362942.html

相关文章

基于单片机的造纸纸浆液位控制系统结构设计

摘要:为适应无人化与高效化制浆造纸生产体系&#xff0c;造纸企业趋于以嵌入式技术优化造纸过 程中的纸浆液位控制系统&#xff0c;以单片机与传感器相互耦合实现纸浆液位控制。本文基于单片机 设计了造纸纸浆液位控制系统&#xff0c;其结构由控制模块、信息采集模块、物联网模…

C#验证字符串是否纯字母:用正则表达式 vs 用Char.IsLetter方法加遍历

目录 一、使用的方法 1.使用正则表达式 2.使用Char.IsLetter方法 二、实例 1. 源码 2.生成效果 一、使用的方法 1.使用正则表达式 使用正则表达式可以验证用户输入的字符串是否为字母。匹配的正则表达式可以是&#xff1a;^[A-Za-z]$、^[A-Za-z]{1,}$、^[A-Za-z]*$。 …

Logback学习

logback 1、logback介绍 Logback是由log4j创始人设计的另一个开源日志组件&#xff0c;性能比log4j要好。 lockback优点&#xff1a; 内核重写、测试充分、初始化内存加载更小&#xff0c;这一切让logback性能和log4j相比有诸多倍的提升。logback非常自然地直接实现了slf4j…

x-shell安装、使用以及配置cuda、cudnn和conda

x-shell安装、使用以及安装最新版本conda x-shell安装远程连接服务器conda安装和环境配置 x-shell安装 x-shell是一款终端模拟软件&#xff0c;用于在Windows界面下远程访问和使用不同系统下的服务器。免费版本下载地址&#xff1a; https://www.xshell.com/zh/free-for-home-…

docker入门教程之将应用程序容器化

将应用程序容器化 在本指南的其余部分中&#xff0c;您将使用在 Node.js 上运行的简单待办事项列表管理器。如果您不熟悉 Node.js&#xff0c;请不要担心。本指南不需要任何 JavaScript 经验。 先决条件 您已安装最新版本的 Docker Desktop。您已经安装了 Git 客户端。您可以…

从编程中理解:大脑的动态更新与信息处理

在深入探讨大脑动态更新与信息处理的过程中,我们可以结合编程语言C#的逻辑来构建一个以金庸武侠世界为背景的故事。设想张无忌在《倚天屠龙记》中学习和掌握九阳真经的过程,我们可以将其类比为一种内存管理和知识积累系统。以下是一个简化版但富含叙事元素的Unity C#脚本示例…

信号传输中串扰的影响.

1.导线间的串扰 当导线之间发生串扰时,一根导线上的信号会影响到另一根信号线,给连接的电路造成干扰。这种现象通常发生在平行的导线之间。在设计设备的布线时,特别要注意低电平模拟信号的传输问题。附近导线对其的串扰常常是系统性能下降的主要原因。因此在布线设计时,必须…

Java线程同步的方法和例子

在Java中&#xff0c;线程同步是一种机制&#xff0c;用于确保多个线程可以安全地访问共享资源&#xff0c;而不会发生数据不一致或数据损坏的情况。线程同步的主要方法包括&#xff1a; synchronized关键字&#xff1a;这是Java中最常用的线程同步方法。它用于方法或代码块&a…