当前位置： 首页 > 编程日记 > 正文

leetcode-452 用最少数量的箭引爆气球

编程日记 2024-04-13 22:30:01

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

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

Example:

输入: [[10,16], [2,8], [1,6], [7,12]]

输出: 2

解释: 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

贪心规律如下：
1.对于某个气球，至少需要使用1只弓箭将它击穿。
2.在这只气球将其击穿的同时，尽可能击穿其他更多的气球

算法思路：

  1. 对各个气球进行排序，按照气球的左端点从小到大排序。
  2. 遍历气球数组，同时维护一个射击区间，在满足可以将当前气球射穿的情况下，尽可能击穿更多的气球，每击穿一个新的气球，更新一次射 击区间(保证射击区间可以将新气球也击穿)。
  3. 如果新的气球没办法被击穿了，则需要增加一名弓箭手，即维护一个新 的射击区间(将该气球击穿)，随后继续遍历气球数组

实现如下:

int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) {return 0;}sort(points.begin(),points.end(),cmp);int num = 1;int shoot_begin = points[0][0];int shoot_end = points[0][1];for (int i = 1; i < points.size(); ++i) {//随着气球数量的递增，区间不断缩小if(shoot_end >= points[i][0]) {shoot_begin = points[i][0];if (shoot_end > points[i][1]) {shoot_end = points[i][1];}} else {//当发现区间的end 小于气球的起始边界，则重新划分区间，箭的数量增加num ++;shoot_begin = points[i][0];shoot_end = points[i][1];}}return num;
}

https://www.dkcj.cn/info/4634.html

相关文章：

ssm 异常捕获 统一处理_SpringMVC 统一异常处理介绍及实战

背景什么是统一异常处理目标统一异常处理实战用 Assert(断言) 替换 throw exception定义统一异常处理器类扩展总结《Java 2019 超神之路》《Dubbo 实现原理与源码解析 —— 精品合集》《Spring 实现原理与源码解析 —— 精品合集》《MyBatis 实现原理与源码解析 —— 精品合集》…

编程日记2024/04/13 22:00:00

【iOS开发】企业版证书（$299）In-House方式发布指南 （转）

一、明确几个概念 1、企业版IDP&#xff1a;即iOS Development Enterprise Program。注意是$299&#xff0f;Year那种&#xff0c;并不是$99/Year的那种。 2、In House&#xff1a;是只企业内部发布&#xff0c;仅限企业内部人员使用。 二、In-House方式特点 1、不能发布到Appl…

编程日记2024/04/13 21:30:00

苹果所有常用证书，appID,Provisioning Profiles配置说明及制作图文教程（精）

概述&#xff1a; 苹果的证书繁锁复杂&#xff0c;制作管理相当麻烦&#xff0c;今天决定重置一个游戏项目中的所有证书&#xff0c;做了这么多次还是感觉很纠结&#xff0c;索性直接记录下来&#xff0c;日后你我他查阅都方便&#xff1b; 首先得描述一下各个证书的定位&#…

编程日记2024/04/13 21:00:00

ES6语法~解构赋值、箭头函数、class类继承及属性方法、map、set、symbol、rest、new.target、 Object.entries......

2015年6月17日 ECMAScript 6发布正式版本 前面介绍基本语法, 后面为class用法及属性方法、set、symbol、rest等语法. 一、基本语法: 1、 定义变量&#xff1a;let 使用var 定义的变量没有{ }限制&#xff0c;在条件中定义的i&#xff0c;全局中都可以使用&#xff0c…

编程日记2024/04/13 20:30:00

读书：历史 -- 东印度公司

浅田实 — 日本 文学博士、英国近世史学专家 东印度公司曾经为英国殖民印度&#xff0c;扮演过冲锋陷阵的历史角色。 富可敌国来形容东印度公司绰绰有余&#xff0c;它的崛起和衰落是时代变迁的缩影。 英国发起的第一次工业革命迫切需要资本的输入和输出来带动蒸汽齿轮得高速转…

编程日记2024/04/13 20:00:00

2014腾讯校园招聘研发笔试题

嘿嘿转载于:https://www.cnblogs.com/churi/p/3969749.html

编程日记2024/04/13 19:30:00

用74l138实现一个一位全减器_用pygame实现一个简单的五子棋游戏

准备python基础相关准备&#xff1a;pygame的基础知识&#xff0c;参考目光博客的“用Python和Pygame写游戏-从入门到精通”安装python 3.8.0 在python官网下载&#xff0c;不多说。安装pygame&#xff0c;命令&#xff1a;pip install pygame如安装较慢&#xff0c;可以参考如…

编程日记2024/04/13 19:00:00

大量LAST_ACK 的分析过程

2019独角兽企业重金招聘Python工程师标准>>> 记录一下自己的思想过程 现象:在netstat的时候发现大量处于LAST_ACK状态的TCP连接&#xff0c;达到在ESTABLISHED状态的90%以上 [rootccsafe ~]# netstat -ant|fgrep ":"|cut -b 77-90|sort |uniq -c …

编程日记2024/04/13 18:30:00

操作系统--内存管理方式

“碎片的内存”描述一个系统中所有不可用的空闲内存。这些资源之所以仍然未被使用&#xff0c;是因为负责分配内存的分配器使这些内存无法使用。这一问题通常都会发生&#xff0c;原因在于空闲内存以小而不连续方式出现在不同的位置。由于分 配方法决定内存碎片是否是一个问题&…

编程日记2024/04/13 18:00:00

题解 UVA11354 【Bond】

并查集按秩合并 传送门 大意&#xff1a;给出一张n个点m条边的无向图&#xff0c; 每条边有一个权值&#xff0c;有q个询问&#xff0c; 每次给出两个点s、t&#xff0c;找一条路&#xff0c; 使得路径上的边的最大权值最小。 我们可以发现&#xff0c;跑最小生成树会跑挂&…

编程日记2024/04/13 17:30:00

读书：有趣 -- 酒鬼与圣徒

编程日记2024/04/13 17:00:00

管理 zabbix_Zabbix 2019 峰会丨看睿象云如何在 Zabbix 中玩转告警

2019年11月29日-30日&#xff0c;为期两天的 Zabbix 大会中国站在北京盛大召开&#xff0c;本届 Zabbix 大会以“新视界&#xff0c;新技术&#xff0c;共建未来新监控!”为主题&#xff0c;为与会人员提供前沿的监控技术学习&#xff0c;多元的行业案例讲解&#xff0c;以及现…

编程日记2024/04/13 16:30:00

Oracle存储过程返回游标实例详解

复制代码 代码如下:CREATE OR REPLACE PROCEDURE PROCSENDEMAIL(P_TXT VARCHAR2, P_SUB VARCHAR2, P_SENDOR VARCHAR2, P_RECEIVER VARCHAR2, P_SERVER VARCHAR2, P_PORT NUMBER DEFAULT 25, P_NEED_SMTP INT DEFAULT 0, P_USER VARCHAR2 DEFAULT NULL, P_PASS VARCHAR2 DEFAUL…

编程日记2024/04/13 16:00:00

03 Django REST Framework 视图和路由

01-DRF中的request 在Django REST Framework中内置的Request类扩展了Django中的Request类&#xff0c;实现了很多方便的功能--如请求数据解析和认证等。 比如&#xff0c;区别于Django中的request从request.GET中获取URL参数&#xff0c;从request.POST中取某些情况下的POST数据…

编程日记2024/04/13 15:30:00

读书：历史 -- 百年战争简史

编程日记2024/04/13 15:00:00

[Quick-x]制作新手引导高亮区域方法之二：裁剪模式

demo下载&#xff1a;https://github.com/chenquanjun/Quick-x-HighlightArea 2、裁剪模式 (1)创建裁剪对象 local bgColor ccc3(255, 0, 0) --非高亮区域颜色local bgOpacity 0.6 --非高亮区域透明度local layerColor CCLayerColor:create(ccc4(bgColor.r, bgColor.g, bgCo…

编程日记2024/04/13 14:30:00

单一窗口关区备案_单一窗口税费支付权限管理

企业需先使用法人卡登录“单一窗口”税费支付系统进行业务权限授权后&#xff0c;才可以使用操作员卡查询、支付、打印税单等。“业务权限授权”模块提供税费支付企业相关业务权限(关区、协议)的授权功能。使用“单一窗口”税费支付系统的部门、用户、角色管理与权限配置等操作…

编程日记2024/04/13 14:00:00

每日一题题目29：五个数字能组成多少互不重复的四位数

#有五个数字&#xff1a;1、2、3、4、5&#xff0c;能组成多少个互不相同且无重复数字的四位数&#xff1f;各是多少&#xff1f; e [] for a in range(1,6):for b in range(1,6):for c in range(1,6):for d in range(1,6):if a!b and a!c and a!d and b!c and b!d and c!d:e.a…

编程日记2024/04/13 13:30:00

读书：历史 -- 空王冠

15世纪50到80年代的玫瑰战争&#xff0c;短短30年间王冠易手7次&#xff0c;成千上万人死于战乱。这段时期&#xff0c;可以算得上英国历史上最混乱、最残暴的历史时期。 英国统治时间最长的金雀花王朝分崩离析&#xff0c;被都铎王朝取代。

编程日记2024/04/13 13:00:00

机器人香囊_青少年智能机器人等级评定~户外营~圆满结束！

2020暑期田园探秘~青少年智能机器人等级评定户外营在8月3日至7日短暂而愉快的欢乐时光中圆满结束了让我们一起来回顾一下这愉快、欢乐、体验成长的时光孩子们在激动的心情下踏上了探秘的欢快路途......初到营地的第一件事~组建团队~首先让大家见识一下我们的团队我们的团队由&a…

编程日记2024/04/13 12:30:00

Linux下DB2数据库安装教程

最近因为工作需要在学习DB2数据库&#xff0c;本教程讲解DB2数据库在inux下的安装步骤。 安装前请查看 DB2版本和许可证 说明来增加了解&#xff0c;先弄明白改安装什么版本&#xff0c;这里我用的是最新的Express-C版本&#xff0c;这个版本是提供给个人学习用的版本。 管理客…

编程日记2024/04/13 12:00:00

Ubuntu 13.04 安装 OpenCV 及试用

2019独角兽企业重金招聘Python工程师标准>>> 暑假来了&#xff0c;项目需要&#xff0c;得学习一下 OpenCV。 首先&#xff0c;是安装问题。我是参照这个网址安装的&#xff1a;http://karytech.blogspot.com/2012/05/opencv-24-on-ubuntu-1204.html&#xff08;在…

编程日记2024/04/13 11:30:00

Python3 调试技巧 —— 死循环

说下Python3不使用gdb的自身调试 前情提要&#xff1a;服务器莫名卡死&#xff0c;用网上的方法用gdb&#xff0c;下载了很多组件&#xff0c;包括那个libpython.py&#xff0c;都没什么用&#xff0c;看不到堆栈&#xff0c;也试了保存core文件等等 大事找官方&#xff1a;官方…

编程日记2024/04/13 11:00:00

读书：历史 -- 奥斯曼帝国六百年

作者&#xff1a;帕特里克贝尔福 &#xff0c;英国历史学家、作家、记者。 本书为作者写作生涯的集大成之作&#xff0c;也是最终之作 一部奥斯曼帝国通史&#xff1a; 伊斯兰教大帝国的兴起、转折、衰败和灭亡 奥斯曼帝国的发家史和我们的大清帝国十分相似&#xff0c;两者都…

编程日记2024/04/13 10:30:00

单片AT89C2051 + SD卡 +　3310LCD = 音乐播放器

http://www.amobbs.com/thread-4503884-1-1.html 这个小玩意&#xff0c;采用 ATMEL 的传统51MCU作主控制芯片&#xff0c;加上SD卡和显示屏&#xff0c;就可以作简单的音乐播放器了&#xff0c;虽然音质不怎么样&#xff0c;不过作为DIY还是蛮有乐趣&#xff0c;希望大家喜欢。…

编程日记2024/04/13 10:00:01

不带头节点的链表有哪些缺点_23张图！万字详解「链表」，从小白到大佬！

链表和数组是数据类型中两个重要又常用的基础数据类型。数组是连续存储在内存中的数据结构&#xff0c;因此它的优势是可以通过下标迅速的找到元素的位置&#xff0c;而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动&#xff0c;为了解决和平衡此问题于是就有了链表…

编程日记2024/04/13 09:30:00

劣质代码评析——《写给大家看的C语言书(第2版)》附录B之21点程序(一)

《写给大家看的C语言书(第2版)》是邮电社图灵公司引进翻译的一本C语言入门书&#xff0c;这是一本垃圾书。搞不清图灵为什么引进了这样一本垃圾书。该书作者基本不懂得C编程技术&#xff0c;书中误导、错谬比比皆是。　　该书的附录B给出了一个21点游戏的代码&#xff0c;这是一…

编程日记2024/04/13 09:00:01

【数学 技巧】2.14计数

有趣的组合数学题&#xff1b;考试时候打满确实挺不容易的…… 题目描述 对于一个 $n$ 阶排列 $p$&#xff0c;我们建立一张无向简单图 $G(p)$&#xff0c;有 $n$ 个节点&#xff0c;标号从 $1$ 到 $n$&#xff0c;每个点向左右两侧最近的比它大的点以及比它小的点连边。 形式化…

编程日记2024/04/13 08:30:00

冒泡排序 算法

算法思路&#xff1a; 从第一个元素开始遍历&#xff0c;比较当前元素和下一个元素的大小不符合&#xff0c;则交换结束最后一个元素&#xff0c;则重新遍历 实现&#xff1a; void bubble_sort(vector<int> &arr) {for (int i 0;i < arr.size() - 1; i) {//交…

编程日记2024/04/13 08:00:00

5单个编译总会编译全部_5分钟读懂JavaScript预编译

大家都知道JavaScript是解释型语言&#xff0c;既然是解释型语言&#xff0c;就是编译一行&#xff0c;执行一行&#xff0c;那又何来预编译一说呢?脚本执行js引擎都做了什么呢&#xff1f;今天我们就来看看吧。1-JavaScript运行三部曲语法分析预编译解释执行语法分析很简单&a…

编程日记2024/04/13 07:30:00