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

【代码随想录训练营】【Day35】第八章|贪心算法|860.柠檬水找零|406.根据身高重建队列|452. 用最少数量的箭引爆气球

柠檬水找零

题目详细:LeetCode.860

一道非常简单的模拟题,根据题目要求编写程序即可:

Java解法(模拟):

class Solution {public boolean lemonadeChange(int[] bills) {int money_5 = 0, money_10 = 0;for(int b : bills){if(b == 5){money_5++;}else if(b == 10){money_10++;money_5--;}else if(b == 20){if(money_10 > 0){money_10--;money_5--;}else{money_5 -= 3;}}if(money_5 < 0 || money_10 < 0)return false;}return true;}
}

根据身高重建队列

题目详细:LeetCode.406

这道题与上一节的练习《分发糖果》有异曲同工之妙,当我们题目有两个维度时,如本题,有两个比较纬度身高h和数量k,所以看到这种题目一定要想先确定哪一个维度,再考虑能不能按照另一个维度重新排列得到正确结果,不能够两个维度条件同时考虑。

解题过程如下:

  • 先确定一个维度:我先按照身高h来排序,身高一定是从大到小排序(身高相同的话则k值较小的站前面),保证前面的节点一定都比当前节点高。
  • 再确定另一维度:
    • 局部最优解:身高从高到低依次按people的k值来插入列表,也就是将k值作为下标来执行插入操作,这样使得people插入后列表仍满足题目的排列要求
    • 全局最优解:全部元素都插入完成,整个队列仍满足题目的排列要求

注意:身高为什么一定是从大到小排?

  • 因为身高从小到大排序,后续完成插入后,结果无法满足题目的排列求,每个节点“前面正好有 k 个身高大于或等于 h 的人”的要求
  • 同理,如果这题要求为“前面正好有 k 个身高大于或等于 h 的人”,则先将身高从小到大排序

Java解法(先按身高排序,再按k值插入):

class Solution {public int[][] reconstructQueue(int[][] peoples) {// 按身高从大到小排序,身高相同则k值小的在前Arrays.sort(peoples, (a, b) -> {if(a[0] == b[0])return a[1] - b[1];return b[0] - a[0];});// 按照k值依次插入List<int[]> ans = new ArrayList<>();for(int[] people : peoples){ans.add(people[1], people);}return ans.toArray(new int[peoples.length][]);}
}

用最少数量的箭引爆气球

题目详细:LeetCode.452

注意本题一个非常坑的测试数据:

[[-2147483646,-2147483645],[2147483646,2147483647]]

在对输入数据进行排序时,需要使用Integer内置的比较器,来防止输入数据溢出。

这道题的思路比较简单,但是我觉得我的表述可能不是很清晰,详细的题解可查阅:《代码随想录》— 用最少数量的箭引爆气球

Java解法(先排序,确定重叠的边界,进而确定箭的数量):

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) -> {// 不能使用 return a[0] - b[0];// 这里需要使用内置的比较器,防止数据溢出return Integer.compare(a[0], b[0]);});// points.length >= 1,所以至少会射出一支箭int count = 1; for(int i = 1; i < points.length; i++){if(points[i - 1][1] < points[i][0])// 如果当前气球的左边界和上一个气球的右边界没有交集// 则说明两个气球没有重叠,需要多射出一支箭count++;else// 如果当前气球的左边界和上一个气球的右边界存在交集// 则当前气球保留一个最小最右边界值,即与上一个气球重叠的最右边界值points[i][1] = Math.min(points[i][1], points[i - 1][1]);}return count;}
}

相关文章:

【代码随想录训练营】【Day35】第八章|贪心算法|860.柠檬水找零|406.根据身高重建队列|452. 用最少数量的箭引爆气球

柠檬水找零 题目详细&#xff1a;LeetCode.860 一道非常简单的模拟题&#xff0c;根据题目要求编写程序即可&#xff1a; Java解法&#xff08;模拟&#xff09;&#xff1a; class Solution {public boolean lemonadeChange(int[] bills) {int money_5 0, money_10 0;fo…...

嵌入式C基础知识(23)

常用C/C代码规范头文件的保护所有的头文件都应该使用#define来避免多次引用&#xff0c;符号格式为&#xff1a;<PROJECT>_<PATH>_<FILE>_H_例如头文件&#xff1a;foo/src/bar/baz.h#ifndef FOO_BAR_BAZ_H_#define FOO_BAR_BAZ_H_...#endif // FOO_BAR_BAZ_…...

一文掌握组织项目等级划分维度,标准和实例

当你遇到多项目怎么管&#xff1f;遇到项目之间的冲突怎么解决&#xff1f;很多公司没有项目优先级的划分&#xff0c;会对企业造成很多严重的问题。首先&#xff0c;会造成不合理的资源分配&#xff1a;缺少项目优先级的情况下&#xff0c;很难确定哪些项目是最重要的&#xf…...

【C++】list的使用和基本迭代器框架的实现 vs和g++下string结构的说明

真正的成熟应该并不是追求完美&#xff0c;而是直面自己的缺憾&#xff0c;这才是生活的本质。 文章目录一、初见list1.list的迭代器失效和基本使用2.list的operations操作接口&#xff08;看起来挺不错的接口&#xff0c;但可惜不怎么实用&#xff09;3.vector和list的排序性能…...

基于深度学习的轴承寿命预测实践,开发CNN、融合LSTM/GRU/ATTENTION

关于轴承相关的项目之前做的大都是故障识别诊断类型的&#xff0c;少有涉及回归预测的&#xff0c;周末的时候宅家发现一个轴承寿命加速实验的数据集就想着拿来做一下寿命预测。首先看下数据集如下&#xff1a;直接百度即可搜到&#xff0c;这里就不再赘述了。Learning_set为训…...

redis进阶:mysql,redis双写一致性,数据库更新后再删除缓存就够了吗?

0. 引言 最近线上的一个状态修改功能出现了问题&#xff0c;一开始是运营找了过来&#xff0c;运营告知某条数据的状态已经开启了的&#xff0c;但是实际使用起来还是没有生效&#xff0c;于是拿到这个问题后&#xff0c;首先就去数据库查了这条数据&#xff0c;发现确实如他所…...

RTOS中互斥量的原理以及应用

互斥量的原理 RTOS中的互斥量是一种同步机制&#xff0c;用于保护共享资源&#xff0c;防止多个任务同时访问该资源&#xff0c;从而避免数据竞争和不一致性。 互斥量的原理是通过对共享资源进行加锁和解锁操作来实现的。 在RTOS中&#xff0c;互斥量通常是一个数据结构&…...

数据分析:基于随机森林(RFC)对酒店预订分析预测

数据分析&#xff1a;基于随机森林(RFC)对酒店预订分析预测 作者&#xff1a;AOAIYI 作者简介&#xff1a;Python领域新星作者、多项比赛获奖者&#xff1a;AOAIYI首页 &#x1f60a;&#x1f60a;&#x1f60a;如果觉得文章不错或能帮助到你学习&#xff0c;可以点赞&#x1f…...

【python】序列(列表、元组)、字典、集合的初步认识

一、序列 序列类型(sequence)&#xff1a;一组有序的数据集&#xff0c;特点是数据之间存在先后关系&#xff0c;通过序号访问 序列包含以下三种类型&#xff1a; 1.字符串&#xff08;str&#xff09;不可修改 2.列表&#xff08;list&#xff09;可修改 3.元组&#xff08;t…...

周赛335(模拟、质因子分解、分组背包)

题解&#xff1a;0x3f https://leetcode.cn/problems/number-of-ways-to-earn-points/solution/fen-zu-bei-bao-pythonjavacgo-by-endlessc-ludl/ 文章目录周赛335[6307. 递枕头](https://leetcode.cn/problems/pass-the-pillow/)模拟[6308. 二叉树中的第 K 大层和](https://le…...

【极致简洁】Python tkinter 实现下载工具,你想要的一键获取

嗨害大家好鸭&#xff01;我是小熊猫~开发环境本次项目案例步骤成品效果【咱追求的就是一个简洁】界面如何开始&#xff1f;1.导入模块2.创建窗口【这步很重要】功能按键1.创建一个下拉列表2.设置下拉列表的值3.设置其在界面中出现的位置 column代表列 row 代表行4.设置下拉列表…...

npm i 安装报错

npm WARN EBADENGINE Unsupported engine { npm WARN… npm WARN deprecated stable0.1.8: Modern JS… 诸如此类的报错。大部分都是因为 node 版本问题&#xff01;比如node版本无法满足&#xff0c;对应项目里需要的那些模块和依赖所需要的条件。 有些模块对node版本是有要…...

原腾讯QQ空间负责人,T13专家,黄希彤被爆近期被裁员,裁员原因令人唏嘘。。...

点击上方“码农突围”&#xff0c;马上关注这里是码农充电第一站&#xff0c;回复“666”&#xff0c;获取一份专属大礼包真爱&#xff0c;请设置“星标”或点个“在看这是【码农突围】的第 431 篇原创分享作者 l 突围的鱼来源 l 码农突围&#xff08;ID&#xff1a;smartyuge&…...

【C++】BloomFilter——布隆过滤器

文章目录一、布隆过滤器概念二、布隆过滤器应用三、布隆过滤器实现1.插入2.查找3.删除四、布隆过滤器优缺五、结语一、布隆过滤器概念 布隆过滤器是由布隆&#xff08;Burton Howard Bloom&#xff09;在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构&#xff0c;特点是…...

【Spring】资源操作管理:Resource、ResourceLoader、ResourceLoaderAware;

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ 资源操作&#xff1a;Spring Resources一、Res…...

【System Verilog基础】automatic自动存储--用堆栈区存储局部变量

文章目录一、C语言的内存分配&#xff1a;BSS、Data、Text、Heap&#xff08;堆&#xff09;、Stack&#xff08;栈&#xff09;1、1、静态内存分配&#xff1a;BSS、Data1、2、程序执行代码&#xff1a;Text1、3、动态内存分配&#xff1a;Heap&#xff08;堆&#xff09;、St…...

看板组件:Bryntum Task Board JS 5.3.0 Crack

一个超级灵活的看板组件&#xff0c;Bryntum Task Board 是一个灵活的看板 Web 组件&#xff0c;可帮助您可视化和管理您的工作。 功能丰富 任务板非常灵活&#xff0c;允许您完全自定义卡片、列和泳道的渲染和样式。借助丰富的 API&#xff0c;您甚至可以在运行时打开或关闭功…...

45 个 Git 经典操作场景,专治不会合代码

git对于大家应该都不太陌生&#xff0c;熟练使用git已经成为程序员的一项基本技能&#xff0c;尽管在工作中有诸如 Sourcetree这样牛X的客户端工具&#xff0c;使得合并代码变的很方便。但找工作面试和一些需彰显个人实力的场景&#xff0c;仍然需要我们掌握足够多的git命令。下…...

MyBatis之动态SQL

目录 一、<if>标签 二、<trim>标签 三、<where>标签 四、<set>标签 五、<foreach>标签 一、<if>标签 当我们在某个平台提交某些信息时&#xff0c;可能都会遇到这样的问题&#xff0c;有些信息是必填信息&#xff0c;有些信息是非必…...

SpringBoot(Tedu)—DAY01——环境搭建

SpringBoot(Tedu)—DAY01——环境搭建 目录SpringBoot(Tedu)—DAY01——环境搭建零、今日目标一、IDEA2021项目环境搭建1.1 通过 ctrl鼠标滚轮 实现字体大小缩放1.2 自动提示设置 去除大小写匹配1.3 设置参数方法自动提示1.4 设定字符集 要求都使用UTF-8编码1.5 设置自动编译二…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

AGain DB和倍数增益的关系

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

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...