当前位置: 首页 > news >正文

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贪心算法 用最少数量的箭引爆气球 和无重叠区间

题目描述 题目分析&#xff1a; x轴向上射箭&#xff0c;12一支&#xff0c;重叠的需要一支&#xff0c;3-8一支&#xff0c;7-16一支 返回2&#xff1b; 就是让重叠的气球尽量在一起&#xff0c;局部最优&#xff1b;用一支弓箭&#xff0c;全局最优就是最少弓箭&#xff1b…...

AMEYA360报道:手机直连卫星通信发展的三个阶段

卫星通信的发展从过去、现在与规划&#xff0c;可以分为三个阶段。手机卫星通信的第一个阶段中&#xff0c;较为典型的有铱星公司、海事卫星电话、天通卫星通信等&#xff0c;终端设备方面已经可以做到手持设备直接通过自带的天线与卫星进行通信。 包括铱星、天通卫星等&#x…...

redis中缓存雪崩,缓存穿透,缓存击穿的原因以及解决方案

一 redis的缓存雪崩 1.1 缓存雪崩 在redis中&#xff0c;新&#xff0c;旧数据交替时候&#xff0c;旧数据进行了删除&#xff0c;新数据没有更新过来&#xff0c;造成在高并发环境下&#xff0c;大量请求查询redis没有数据&#xff0c;直接查询mysql&#xff0c;造成mysql的…...

ChatGPT火热之下的冷思考

作为一款基于人工智能的自然语言处理(NLP)​​聊天机器人​​程序&#xff0c;ChatGPT通过大量来自互联网的文本进行训练&#xff0c;并使用深度学习和机器学习算法来理解用户的问题并提供准确的回答。并且&#xff0c;ChatGPT还内置了情感分析、关键字提取和实体识别等功能&am…...

查看docker容器启动参数

查看docker启动参数 1、查看docker容器的自启动策略2、查看docker容器的日志滚动清理策略 以下配置命令以redis容器为例 1、查看docker容器的自启动策略 docker inspect --format{{json .HostConfig.RestartPolicy}} redis输出的name是always 表示此容器是开机自启动的&#x…...

对Webpack的理解

Webpack是目前比较物流的前端构建工具&#xff0c;它基于入口&#xff0c;用不同的Loader来处理不同的文件 Webpack的核心概念 Entry&#xff1a;入口&#xff0c;Webpack执行构建的第一步将从Entry开始&#xff0c;可抽象成输入。告诉Webpack要使用哪个模块作为构建项目的起…...

使用wxPython和pillow开发拼图小游戏(四)

上一篇介绍了使用本地图片来初始化游戏的方法&#xff0c;通过前边三篇&#xff0c;该小游戏的主要内容差不多介绍完了&#xff0c;最后这一篇来介绍下游戏用时的计算、重置游戏和关闭窗口事件处理 游戏用时的计算 对于游戏用时的记录&#xff0c;看过前几篇的小伙伴可能也发现…...

XGBoost实例——皮马印第安人糖尿病预测和特征筛选

利用皮马印第安人糖尿病数据集来预测皮马印第安人的糖尿病&#xff0c;以下是数据集的信息&#xff1a; Pregnancies&#xff1a;怀孕次数Glucose&#xff1a;葡萄糖BloodPressure&#xff1a;血压 (mm Hg)SkinThickness&#xff1a;皮层厚度 (mm)Insulin&#xff1a;胰岛素 2…...

使用MQ发送对象错误

说明&#xff1a;使用RabbitMQ发送消息&#xff0c;消息是对象&#xff0c;出现下面这样的错误&#xff1b; 错误信息&#xff1a;Caused by: com.fasterxml.jackson.databind.exc.InvalidDefinitionException: Cannot construct instance of com.hmall.item.pojo.Item (no Cr…...

安装和卸载docker,详细教程

安装docker ############################################################################# 安装&#xff1a; 1、Docker要求CentOS系统的内核版本高于 3.10 &#xff0c;通过 uname -r 命令查看你当前的内核版本是否支持安账docker 2、更新yum包&#xff1a;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)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于ssm的人才公寓管理系统。技术交流和部署相关看文章末尾&#xff01; 开发环境&#xff1a; 后端&#xff1a; 开发语言&#xff1a;Java 框架&…...

git使用记录

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、常用git命令总结 前言 一、常用git命令 git --version # mkdir my-project cd my-project git status # 这一步显然没东西 git init # 创建 git status #…...

Spring MVC异步上传、跨服务器上传和文件下载

一、异步上传 之前的上传方案&#xff0c;在上传成功后都会跳转页面。而在实际开发中&#xff0c;很多情况下上传后不进行跳转&#xff0c;而是进行页面的局部刷新&#xff0c;比如&#xff1a;上传头像成功后将头像显示在网页中。这时候就需要使用异步文件上传。 1.1 JSP页面 …...

性能测试之并发用户数的估计

在计算并发用户数之前&#xff0c;需要先了解2个概念。 并发用户&#xff1a;指的是现实系统中同时操作业务的用户&#xff0c;在性能测试工具中一般称为虚拟用户。并发用户这些用户的最大特征是和服务器产生了交互&#xff0c;这种交互既可以是单向的传输数据&#xff0c;也可…...

【全方位解析】如何获取客户端/服务端真实 IP

一、应用场景 1.比如在投票系统开发中&#xff0c;为了防止刷票&#xff0c;我们需要限制每个 IP 地址只能投票一次 2.当网站受到诸如 DDoS&#xff08;Distributed Denial of Service&#xff0c;分布式拒绝服务攻击&#xff09;等攻击时&#xff0c;我们需要快速定位攻击者…...

Ceph简介和特性

Ceph是一个多版本存储系统&#xff0c;它把每一个待管理的数据流(例如一个文件) 切分为一到多个固定大小的对象数据&#xff0c;并以其为原子单元完成数据存取。 对象数据的底层存储服务是由多个主机 (host) 组成的存储集群&#xff0c;该集群也被称之为 RADOS (ReliableAutoma…...

Python基本语法之符号使用

好久没有和小伙伴们更新python了&#xff0c;我对于此感到抱歉以后有时间尽量多更新 目录 一. 标识符 A.定义&#xff1a; B.使用特点 C.Python标识符&#xff0c;进一步探讨以下几个方面的详细内容&#xff1a; 1. 规则和约定&#xff1a; 2. 有效的标识符示例&#xff1…...

前端vue部署到nginx并且配置https安全证书全流程

说明一下&#xff1a; 本人原本使用的是docker安装nginx通过挂载实现部署&#xff0c;但是出现了很多bug&#xff08;例如部署安全证书后还是无法访问&#xff09;&#xff0c;所以困扰了很久&#xff0c;最后改为本地安装nginx&#xff0c;最终在不懈的努力下终于按照好了&…...

三子棋(超详解+完整码源)

三子棋 前言一&#xff0c;游戏规则二&#xff0c;所需文件三&#xff0c;创建菜单四&#xff0c;游戏核心内容实现1.棋盘初始化1.棋盘展示3.玩家下棋4.电脑下棋5.游戏胜负判断6.game&#xff08;&#xff09;函数内部具体实现 四&#xff0c;游戏运行实操 前言 C语言实现三子棋…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...