day31贪心算法 用最少数量的箭引爆气球 和无重叠区间
题目描述

题目分析:

x轴向上射箭,12一支,重叠的需要一支,3-8一支,7-16一支 返回2;
就是让重叠的气球尽量在一起,局部最优;用一支弓箭,全局最优就是最少弓箭;
如何去寻找重叠的气球?和记录弓箭数?
1.对所有气球排序;(左边界排序如上图);
2. if 如果第i个气球的左边界大于第i-1个气球的右边界;即point[i][0] > point[i-1][1] 比如上图中3 6 的左边界3大于右边界1 2 的右边界2;那么弓箭数++;
3.else 就是重叠 右边界取最小值;

如图36 48重叠,右边界取6 8 的最小值6作为重叠的右边界;
else 逻辑: a: 更新右边界;points[i][1] = min(points[i-1][1] ,points[i][1] );
b:拿这个右边界和下一个气球比较;
int cmp(const void *a, const void *b)
{int *x = *(int **)a;int *y = *(int **)b;if (x[0] == y[0]) {return x[1] > y[1];}return x[0] > y[0];
}int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){//将points数组作升序排序qsort(points, pointsSize, sizeof(points[0]),cmp);int arrowNum = 1;int i = 1;for(i = 1; i < pointsSize; i++) {//若前一个气球与当前气球不重叠,证明需要增加箭的数量if(points[i][0] > points[i-1][1])arrowNum++;else//若前一个气球与当前气球重叠,判断并更新最小的x_endpoints[i][1] = fmin(points[i-1][1] ,points[i][1] );}return arrowNum;
}
题目描述

分析:
左边界排序,
if nums[i][0] >= nums[i-1][1] i的左边界大于i-1的右边界表示没有重叠;
else 重叠 cnt++; 右边界也是取最小值,和上一题一样; nums[i][1] = min(nums[i-1][1],nums[i][1]);
代码一
int cmp(const void *a, const void *b)
{int *x = *(int **)a;int *y = *(int **)b;if (x[0] == y[0]) {return x[1] > y[1];}return x[0] > y[0];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize == 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int *),cmp);int count = 0;for (int i = 1; i < intervalsSize; i++) { // i 和 i-1if (intervals[i][0] < intervals[i-1][1]) {//重叠count++;//后面区间和当前区间是否重叠 更新右边界intervals[i][1] = fmin(intervals[i][1], intervals[i-1][1]);}}// 返回重复区间数return count;
}
代码二
int cmp(const void *pa, const void *pb)
{return (*(int**)pa)[1] - (*(int**)pb)[1];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize == 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int*), cmp);int x_end = intervals[0][1];int start;int count = 1;for (int i = 1; i < intervalsSize; i++) {start = intervals[i][0];if (start >= x_end) {// 不相交count++;// 更新不重复区间endx_end = intervals[i][1];}}// 返回重复区间数return intervalsSize - count;
}
相关文章:
day31贪心算法 用最少数量的箭引爆气球 和无重叠区间
题目描述 题目分析: x轴向上射箭,12一支,重叠的需要一支,3-8一支,7-16一支 返回2; 就是让重叠的气球尽量在一起,局部最优;用一支弓箭,全局最优就是最少弓箭;…...
AMEYA360报道:手机直连卫星通信发展的三个阶段
卫星通信的发展从过去、现在与规划,可以分为三个阶段。手机卫星通信的第一个阶段中,较为典型的有铱星公司、海事卫星电话、天通卫星通信等,终端设备方面已经可以做到手持设备直接通过自带的天线与卫星进行通信。 包括铱星、天通卫星等&#x…...
redis中缓存雪崩,缓存穿透,缓存击穿的原因以及解决方案
一 redis的缓存雪崩 1.1 缓存雪崩 在redis中,新,旧数据交替时候,旧数据进行了删除,新数据没有更新过来,造成在高并发环境下,大量请求查询redis没有数据,直接查询mysql,造成mysql的…...
ChatGPT火热之下的冷思考
作为一款基于人工智能的自然语言处理(NLP)聊天机器人程序,ChatGPT通过大量来自互联网的文本进行训练,并使用深度学习和机器学习算法来理解用户的问题并提供准确的回答。并且,ChatGPT还内置了情感分析、关键字提取和实体识别等功能&am…...
查看docker容器启动参数
查看docker启动参数 1、查看docker容器的自启动策略2、查看docker容器的日志滚动清理策略 以下配置命令以redis容器为例 1、查看docker容器的自启动策略 docker inspect --format{{json .HostConfig.RestartPolicy}} redis输出的name是always 表示此容器是开机自启动的&#x…...
对Webpack的理解
Webpack是目前比较物流的前端构建工具,它基于入口,用不同的Loader来处理不同的文件 Webpack的核心概念 Entry:入口,Webpack执行构建的第一步将从Entry开始,可抽象成输入。告诉Webpack要使用哪个模块作为构建项目的起…...
使用wxPython和pillow开发拼图小游戏(四)
上一篇介绍了使用本地图片来初始化游戏的方法,通过前边三篇,该小游戏的主要内容差不多介绍完了,最后这一篇来介绍下游戏用时的计算、重置游戏和关闭窗口事件处理 游戏用时的计算 对于游戏用时的记录,看过前几篇的小伙伴可能也发现…...
XGBoost实例——皮马印第安人糖尿病预测和特征筛选
利用皮马印第安人糖尿病数据集来预测皮马印第安人的糖尿病,以下是数据集的信息: Pregnancies:怀孕次数Glucose:葡萄糖BloodPressure:血压 (mm Hg)SkinThickness:皮层厚度 (mm)Insulin:胰岛素 2…...
使用MQ发送对象错误
说明:使用RabbitMQ发送消息,消息是对象,出现下面这样的错误; 错误信息:Caused by: com.fasterxml.jackson.databind.exc.InvalidDefinitionException: Cannot construct instance of com.hmall.item.pojo.Item (no Cr…...
安装和卸载docker,详细教程
安装docker ############################################################################# 安装: 1、Docker要求CentOS系统的内核版本高于 3.10 ,通过 uname -r 命令查看你当前的内核版本是否支持安账docker 2、更新yum包:sudo yum -y up…...
RabbitMQ的确认机制
RabbitMQ的确认机制 生产者确认 public class ProductionMessageConfirm {public static void Send(){ConnectionFactory factory new ConnectionFactory();factory.HostName "localhost";//RabbitMQ服务在本地运行factory.UserName "guest";//用户名…...
java项目之人才公寓管理系统(ssm+mysql+jsp)
风定落花生,歌声逐流水,大家好我是风歌,混迹在java圈的辛苦码农。今天要和大家聊的是一款基于ssm的人才公寓管理系统。技术交流和部署相关看文章末尾! 开发环境: 后端: 开发语言:Java 框架&…...
git使用记录
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、常用git命令总结 前言 一、常用git命令 git --version # mkdir my-project cd my-project git status # 这一步显然没东西 git init # 创建 git status #…...
Spring MVC异步上传、跨服务器上传和文件下载
一、异步上传 之前的上传方案,在上传成功后都会跳转页面。而在实际开发中,很多情况下上传后不进行跳转,而是进行页面的局部刷新,比如:上传头像成功后将头像显示在网页中。这时候就需要使用异步文件上传。 1.1 JSP页面 …...
性能测试之并发用户数的估计
在计算并发用户数之前,需要先了解2个概念。 并发用户:指的是现实系统中同时操作业务的用户,在性能测试工具中一般称为虚拟用户。并发用户这些用户的最大特征是和服务器产生了交互,这种交互既可以是单向的传输数据,也可…...
【全方位解析】如何获取客户端/服务端真实 IP
一、应用场景 1.比如在投票系统开发中,为了防止刷票,我们需要限制每个 IP 地址只能投票一次 2.当网站受到诸如 DDoS(Distributed Denial of Service,分布式拒绝服务攻击)等攻击时,我们需要快速定位攻击者…...
Ceph简介和特性
Ceph是一个多版本存储系统,它把每一个待管理的数据流(例如一个文件) 切分为一到多个固定大小的对象数据,并以其为原子单元完成数据存取。 对象数据的底层存储服务是由多个主机 (host) 组成的存储集群,该集群也被称之为 RADOS (ReliableAutoma…...
Python基本语法之符号使用
好久没有和小伙伴们更新python了,我对于此感到抱歉以后有时间尽量多更新 目录 一. 标识符 A.定义: B.使用特点 C.Python标识符,进一步探讨以下几个方面的详细内容: 1. 规则和约定: 2. 有效的标识符示例࿱…...
前端vue部署到nginx并且配置https安全证书全流程
说明一下: 本人原本使用的是docker安装nginx通过挂载实现部署,但是出现了很多bug(例如部署安全证书后还是无法访问),所以困扰了很久,最后改为本地安装nginx,最终在不懈的努力下终于按照好了&…...
三子棋(超详解+完整码源)
三子棋 前言一,游戏规则二,所需文件三,创建菜单四,游戏核心内容实现1.棋盘初始化1.棋盘展示3.玩家下棋4.电脑下棋5.游戏胜负判断6.game()函数内部具体实现 四,游戏运行实操 前言 C语言实现三子棋…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
