当前位置: 首页 > 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语言实现三子棋…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...