[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;

    }
}

 

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

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

相关文章

快速入门FreeRTOS心得(正点原子学习版)

对于FreeROTS&#xff0c;我第一反应想到的就是通信里的TDM&#xff08;时分多址&#xff09;。不同任务给予分配不同的时间间隔&#xff0c;也就是任务之间在每个timeslot都在来回切换。 这里有重要的一点&#xff0c;就是中断要短小&#xff0c;优先级是自高到底进行打断。 …

204.贪心算法:分发饼干(力扣)

以下来源于代码随想录 class Solution { public:int findContentChildren(vector<int>& g, vector<int>& s) {// 对孩子的胃口进行排序sort(g.begin(), g.end());// 对饼干的尺寸进行排序sort(s.begin(), s.end());int index s.size() - 1; // 从最大的饼…

大数据招商的应用场景及实施路径有哪些?

当下&#xff0c;我国已经进入数字经济与实体经济融合发展的新阶段&#xff0c;数字技术和数字化转型落地日臻成熟&#xff0c;数据要素价值释放深入到了我国各个领域的发展&#xff0c;招商引资也不例外&#xff0c;在传统招商模式效果日渐甚微的大环境下&#xff0c;大数据招…

面试题 4:阐述以下方法 @classmethod, @staticmethod, @property?

欢迎莅临我的博客 &#x1f49d;&#x1f49d;&#x1f49d;&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

数据大小端问题

文章目录 大小端前言函数引用(接下来使用此函数对高低位进行切换)先看截取的对于大小端的定义大小端数据的直观理解[重点] 对uchar数组进行取操作定义一个uint8_t的数组观察起内部内存尝试使用uint32_t 每次区 1、2、3、4byte数据 提升经过上面的介绍一定对大小端有了一定的了解…

2.3 主程序和外部IO交互 (文件映射方式)----IO Server实现

2.3 主程序和外部IO交互 &#xff08;文件映射方式&#xff09;----IO Server C实现 效果显示 1 内存共享概念 基本原理&#xff1a;以页面为单位&#xff0c;将一个普通文件映射到内存中&#xff0c;达到共享内存和节约内存的目的&#xff0c;通常在需要对文件进行频繁读写时…

基于OpenMV识别数字及程序说明

OpenMV简介 OpenMV是一个开源、低成本且功能强大的机器视觉模块。它基于STM32F427CPU&#xff0c;集成了OV7725摄像头芯片&#xff0c;能在小巧的硬件模块上&#xff0c;用C语言高效地实现核心机器视觉算法&#xff0c;并提供了Python编程接口&#xff0c;使得图像处理的复杂度…

【教程】lighttpd配置端口反向代理

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 1、修改配置文件&#xff1a; sudo vim /etc/lighttpd/lighttpd.conf2、先添加mod_proxy&#xff1a; 3、然后添加端口映射&#xff1a; 4、保存&…

2024年07年01日 Redis数据类型以及使用场景

String Hash List Set Sorted Set String&#xff0c;用的最多&#xff0c;对象序列化成json然后存储 1.对象缓存&#xff0c;单值缓存 2.分布式锁 Hash&#xff0c;不怎么用到 1.可缓存经常需要修改值的对象&#xff0c;可单独对对象某个属性进行修改 HMSET user {userI…

Transformation(转换)开发-switch/case组件

一、switch/case组件-条件判断 体育老师要做一件非常重要的事情&#xff1a;判断学生是男孩还是女孩、或者是蜘蛛&#xff0c;然后让他们各自到指定的队伍中 体育老师做的事情&#xff0c;我们同样也会在Kettle中会经常用来。在Kettle中&#xff0c;switch/case组件可以来做类似…

河南特岗教师报名流程及免冠照片电子版制作要求

2024年河南特岗教师招聘季又来啦&#xff01;想要成为孩子们心中的超级英雄吗&#xff1f;想要在教育的田野上播种希望吗&#xff1f;那就不要错过这次机会&#xff0c;今年全省共招聘特岗教师3495名&#xff08;具体岗位设置参见《河南省2024年特岗教师招聘岗位设置》&#xf…

盒子模型(笔记)

盒子模型 盒子模型的属性 padding属性 内边距&#xff1a;盒子的边框到内容的距离 /*每个方向内边距*/padding-top: 20px;padding-left:20px;padding-bottom:20px;padding-right: 20px; /*每个方向内边距的第二种方法*/ /* 顺序依次是上左右下*/padding: 10px 20px 30px 4…

02:vim的使用和权限管控

vim的使用 1、vim基础使用1.1、vim pathname 2、vim高级用法2.1、查找2.2、设置显示行号2.3、快速切换行2.4、 行删除2.5、行复制粘贴 3、权限管理3.1、普通用户和特权用户3.2、文件权限表示 vim是Linux中的一种编辑器&#xff0c;类似于window中的记事本&#xff0c;可以对创建…

TP8/6 更改后台入口地址admin改为myadmin 隐藏真实后台网址

原来www.xxx.com/admin 改后www.xxx.com/myadmin config/app.php // 应用映射&#xff08;自动多应用模式有效&#xff09;app_map > [admintest>admin],

【前端VUE】VUE3第一节—vite创建vue3工程

什么是VUE Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&#xff0…

卷积层里的填充和步幅

一、定义 1、对于卷积&#xff0c;我们另一个超参数是核的大小&#xff0c;通常使用的卷积核是33或者55&#xff0c;很少用偶数核 2、填充是为了让输出不变或者变大&#xff0c;是为了在输入不太大&#xff0c;又能使模型足够深的情况下使用 3、填充&#xff1a;在输入周围添…

开源软件开发平台哪家好?

进行数字化转型&#xff0c;离不开低代码技术平台等软件产品的加持与助力。因为它更好操作、更灵活、易维护等优势特点突出&#xff0c;在推动企业实现流程化办公的过程中助力明显&#xff0c;作用大&#xff0c;深得客户喜爱。那么&#xff0c;低代码技术平台、开源软件开发平…

居然这么简单就能实现扫雷游戏!

目录 一.思路 1.成果展示 2.思路 二.具体操作 1.创建"棋盘" 2.初始化雷 3.布置雷 4.打印 5.排除雷 三.代码实现 1.test.c文件 2.thunder.h文件 3.thunder.c文件 Hello&#xff0c;大家好&#xff0c;今天我们来实现扫雷游戏&#xff0c;希望这一篇博客能给带给大家一…

HCIA是什么等级的证书

HCIA是华为认证体系中的初级认证&#xff0c;主要用于表明持有者在某一技术领域达到了工程师级别的能力证明。这种认证主要涉及到ICT(信息技术基础设施与通信)设备的安装、配置、运行以及故障排除等方面。 HCIA证书的作用 HCIA证书是进入IT行业的一个初步资格证书&#xff0c;它…

昇思25天学习打卡营第6天|数据变换 Transforms

学习目标&#xff1a;熟练掌握数据变换操作 熟悉mindspore.dataset.transforms接口 实践掌握常用变换 昇思大模型平台学习心得记录&#xff1a; 一、关于mindspore.dataset.transforms 1.1 变换 mindspore.dataset.transforms.Compose将多个数据增强操作组合使用。 mindspo…