代码随想录算法训练营第三十四天| 860.柠檬水找零 、406.根据身高重建队列 、452. 用最少数量的箭引爆气球

文章目录

  • 1.柠檬水找零
  • 2.根据身高重建队列
  • 3.用最少数量的箭引爆气球


1.柠檬水找零

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true,否则返回 false

示例 1:

  • 输入:bills = [5,5,5,10,20]
  • 输出:true
  • 解释:
    前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
    第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
    第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
    由于所有客户都得到了正确的找零,所以我们输出 true。

示例 2:

  • 输入:bills = [5,5,10,10,20]
  • 输出:false
  • 解释:
    前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
    对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
    对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
    由于不是每位顾客都得到了正确的找零,所以答案是 false。

提示:

  • 1 <= bills.length <= 10^5
  • bills[i] 不是 5 就是 10 或是 20

只需要维护三种金额的数量5 10 20

  1. 情况一: 账单是5,直接收下。
  2. 情况二: 账单是10,消耗一个5,增加一个10
  3. 情况三: 账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

代码如下:

class Solution {
private:static bool cmp(vector<int>& a, vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1;for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {result++;}else {points[i][1] = min(points[i - 1][1], points[i][1]);}}return result;}
};

2.根据身高重建队列

假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi,前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

示例 1:

  • 输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
  • 输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
  • 解释:
    • 编号为 0 的人身高为 5,没有身高更高或者相同的人排在他前面。
    • 编号为 1 的人身高为 7,没有身高更高或者相同的人排在他前面。
    • 编号为 2 的人身高为 5,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。
    • 编号为 3 的人身高为 6,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
    • 编号为 4 的人身高为 4,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。
    • 编号为 5 的人身高为 7,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
      因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2:

  • 输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
  • 输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示:

  • 1 <= people.length <= 2000
  • 0 <= hi <= 10^6
  • 0 <= ki < people.length
  • 题目数据确保队列可以被重建

有两个维度权衡,需要先确定一个维度,再确定另一个,我们可以先用身高排序,然后按照k为下标重新插入排序
代码如下

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}
};

3.用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points,其中 points[i] = [xstart, xend] 表示水平直径在 xstartxend 之间的气球。你不知道气球的确切 y 坐标。

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

给你一个数组 points,返回引爆所有气球所必须射出的最小弓箭数。

示例 1:

  • 输入:points = [[10,16],[2,8],[1,6],[7,12]]
  • 输出:2
  • 解释:气球可以用2支箭来爆破:
    • x = 6 处射出箭,击破气球 [2,8][1,6]
    • x = 11 处发射箭,击破气球 [10,16][7,12]

示例 2:

  • 输入:points = [[1,2],[3,4],[5,6],[7,8]]
  • 输出:4
  • 解释:每个气球需要射出一支箭,总共需要4支箭。

示例 3:

  • 输入:points = [[1,2],[2,3],[3,4],[4,5]]
  • 输出:2
  • 解释:气球可以用2支箭来爆破:
    • x = 2 处发射箭,击破气球 [1,2][2,3]
    • x = 4 处射出箭,击破气球 [3,4][4,5]

提示:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= xstart < xend <= 2^31 - 1

局部最优: 当气球出现重叠,一起射,所用弓箭最少。全局最优: 把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠,需要对数组进行排序。可以先对右边界进行排序。然后用第一个右边界第二个左边界比较,第一个右边界大与第二个左边界则重叠,此时可以少射一只箭count++。再次用第一个右边界第三个左边界比较,若此时第一个右边界小于第三个左边界,则此时更新右边界为第三个边界的右边界。

在这里插入图片描述

代码如下

class Solution {
private:static bool cmp(vector<int>& a, vector<int>& b) {return a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp);int result = 1;for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {result++;}else {points[i][1] = min(points[i - 1][1], points[i][1]);}}return result;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/269919.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(四)关系模型之关系代数

4.1关系代数概述 基于集合&#xff0c;提供了一系列的关系代数操作&#xff1a;并、差、笛卡尔积(广义积)、 选择、投影和更名等基本操作以及交、 连接和关系除等扩展操作&#xff0c;是一种集合思维的操作语言。关系代数操作以一个或多个关系为输入&#xff0c;结果是一个新的…

食品加工生产污废水处理如何达标排放

食品加工行业作为一个重要的工业部门&#xff0c;在生产过程中产生大量的污废水。合理、高效地处理这些污废水&#xff0c;实现达标排放&#xff0c;是保护环境和促进可持续发展的重要举措。本文将探讨食品加工生产污废水处理的方法和措施&#xff0c;以达到达标排放的目标。 首…

FreeRTOS操作系统学习——内存管理

C库函数与FreeRTOS内存管理区别 在C语言的库函数中&#xff0c;有mallc、free等函数可以申请以及释放内存空间&#xff0c;那么这为什么不适用于FreeRTOS的内存管理呢&#xff1f; 不适合用在资源紧缺的嵌入式系统中这些函数的实现过于复杂、占据的代码空间太大并非线程安全的…

小黑长沙特种兵归来,身体比较虚弱的js逆向烧脑之路:招标网搜索数据获取

通过有道翻译逆向的初步尝试&#xff0c;这次尝试一下招标网的数据获取感觉轻松了许多!!加油小黑黑 寻找接口地址(通过响应部分&#xff0c;推断出该部分为搜索数据获取接口) 复制curl&#xff0c;构造Python请求信息 进入https://curlconverter.com/python/&#xff0c;通过c…

HarmonyOS创建项目和应用—设置数据处理位置

项目和应用介绍 关于项目 项目是资源、应用的组织实体。资源包括服务器、数据库、存储&#xff0c;以及您的应用、终端用户的数据等。在您使用部分服务时&#xff0c;您是数据的控制者&#xff0c;数据将按照您设置的数据处理位置来存储在指定区域。 通常&#xff0c;您不需…

HTTPS如何保证数据传输的安全性 以及CA签发证书验签

暴力输出&#xff1a; 越看会越深入&#xff0c;睡前难以想通&#xff0c;后深入研究。得之。 有问题 请留言。 ----------追求内心的富足与平和。日行一善。 亓苏姑娘

停止Tomcat服务的方式

运行脚本文件停止 运行Tomcat的bin目录中提供的停止服务的脚本文件 关闭命令 # sh方式 sh shutdown.sh# ./方式 ./shutdown.sh操作步骤 运行结束进程停止 查看Tomcat进程&#xff0c;获得进程id kill进程命令 # 执行命令结束进程 kill -9 65358 操作步骤 注意 kill命令是…

相机类型的分辨率长宽、靶面尺寸大小、像元大小汇总

镜头的靶面尺寸大于等于相机靶面尺寸。 相机的芯片长这样&#xff0c;绿色反光部分&#xff08;我的手忽略&#xff09;&#xff1a; 基本所有像素的相机的靶面大小都可以在这个表格里面找到。 镜头的靶面尺寸在镜头外表上可以找到&#xff0c;选型很重要&#xff01;

如何在2.2.1版Aduino IDE中开发ESP32

ESP32芯片集成了WIFI和蓝牙&#xff0c;而且关于生态也很不错&#xff0c;越来越多的学习者和开发者选择此类芯片&#xff0c;而不像用keil开发STM32或者51一样&#xff0c;ESP32虽然也有官方的ESP32-IDF开发软甲&#xff0c;但是经过我个人的实操体验&#xff0c;不适合小白或…

Blender和3ds Max哪个会是行业未来?

Blender和3ds Max都是很强大的三维建模和渲染软件&#xff0c;各有各的好处。选择哪个软件更好&#xff0c;要看你的需求、预算、技术水平以及行业趋势等因素。 Blender最大的优点是免费且开源&#xff0c;这对预算有限的个人和小团队来说很有吸引力。它有很多建模工具和功能&…

Unity编辑器功能Inspector快捷自动填充数据和可视化调试

我们有时候可能需要在面板增加一些引用&#xff0c;可能添加脚本后要手动拖动&#xff0c;这样如果有大量的脚本拖动也是不小的工作量 实例 例如&#xff1a;我的脚本需要添加一个Bone的列表&#xff0c;一个个拖动很麻烦。 实现脚本 我们可以用这样的脚本来实现。 public…

GFP-GAN环境搭建推理测试

引子 近期&#xff0c;文生图&#xff0c;wav2lip很火&#xff0c;文生图&#xff0c;见识的太多&#xff0c;不多说了。wav2lip其通过语音驱动唇部动作并对视频质量进行修复&#xff0c;里面一般涉及到三个步骤&#xff0c;文本到语音转化&#xff0c;语音驱动唇部动作&#…

[XJTU-SY-BD]基础03 - 包络谱生成

1.分析结果 包络图是第三行。第一行水平时域信号&#xff0c;第二行垂直时域信号&#xff0c;第三行对第1行信号在故障频点包络计算后的结果。 上方是最终的视图。右下角我把光标对准了低频位置的那个故障峰&#xff0c;与理论值是一致的. 2.源码 2.1 测试例程源码 import …

Nature 研究亮点(Volume 626 Issue 8001, 29 February 2024)

文章目录 激光雕刻肥皂膜卵细胞的回收系统巴斯克语的起源产后抑郁症的治疗 激光雕刻肥皂膜 研究者&#xff1a;Haitao Xu 和 Yu Zhao&#xff0c;清华大学&#xff0c;北京。 发现&#xff1a;在特定条件下&#xff0c;可以使用激光在肥皂膜上进行雕刻。肥皂膜由洗涤剂分子&am…

护眼灯哪个牌子好?热门护眼台灯测评对比:明基/书客/柏曼,速度戳进来了解!

近年来&#xff0c;市场上出现了大量新型护眼台灯&#xff0c;让消费者在面对众多选择时感到困惑。在选购护眼台灯的时候&#xff0c;我们需要谨慎考虑&#xff0c;有些护眼台灯因为不合格&#xff0c;在使用过程中发热可能会产生有毒物质&#xff0c;对健康造成不良影响。那么…

Nginx使用—http基础知识

web访问流程 当我们在客户端通过浏览器输入网址的时候&#xff0c;这时候是访问不到服务器的&#xff0c; 先会去找到DNS解析服务器&#xff0c;DNS解析服务器返回IP地址&#xff0c; 客户端通过http协议向服务端发送请求&#xff0c;服务器响应请求并返回对应的资源给客户端&a…

TruEra

文章目录 关于 TruEra关于 TruLens 关于 TruEra TruEra Gen AI Observability and LLM Evaluation​ Monitor, evaluate, and debug your LLM and Gen AI apps. All part of Full Lifecycle AI Observability from TruEra. 官网&#xff1a;https://truera.comgithub : https…

旺泓_光感WH3620_数字RGBW-IR色彩传感器

由工采网代理的WH3620是一种基于颜色的光到数字转换器;它集光电二极管、电流放大器、模拟电路和数字信号处理器于一体&#xff1b;提供红、绿、蓝、白和红外光传感&#xff1b;能调节屏幕或灯光白平衡&#xff1b;各通道同时并行输出&#xff0c;因此在白光LED、CWF、TL84、D65…

本机虚拟机centos7设置固定ip

一、配置虚拟机网络 1、点击编辑 2、点击更改设置 记住子网地址&#xff1a;192.168.121.0 点击确定 二、配置虚拟机网络配置文件 首先进去root中&#xff0c;然后进入vim编辑器中 (1)su - root (2) vim /etc/sysconfig/network-scripts/ifcfg-ens33 在VIM编辑器中修改并添加…

约课小程序有哪些功能

​约课小程序为教育机构、教师和学生提供了便捷的预约和管理服务&#xff0c;有效提升了教学效率和用户体验。在这篇文章中&#xff0c;我们将介绍约课小程序常见的功能&#xff0c;帮助教育机构更好地了解如何利用小程序来提升服务质量和管理效率。 1. **课程预约功能**&…