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

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...