当前位置: 首页 > 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 设置自动编译二…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...