代码随想录算法训练营第29天|LeetCode 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列
1. LeetCode 134. 加油站
题目链接:https://leetcode.cn/problems/gas-station/description/
文章链接:https://programmercarl.com/0134.加油站.html
视频链接:https://www.bilibili.com/video/BV1jA411r7WX

思路:
贪心:
局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行。
全局最优:找到可以跑一圈的起始位置。
如果从起始位置i开始跑一圈的过程中不出现累加和curSum小于0的情况就说明该起始位置i可以跑一圈。若出现,则说明起始位置i到出现累加和小于0的位置j之间不存在合适的起始位置,新的起始位置从j+1开始。
解法:
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int start = 0;int curSum = 0;int totalSum = 0;for (int i=0;i<gas.length;i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {start = i + 1;curSum = 0;}}if (totalSum < 0) {return -1;}return start;}
}
代码解析:
有一个关键的变量,即:totalSum。用其判断整个数组有没有起始位置,若小于0,则表示没有起始位置;若大于0,则表示有起始位置。
在如下for循环中只需要判断半圈是否是有起始位置就可以,因为另一半肯定没有。
如,在i位置的curSum<0,则说明[0,i]区间内肯定没有起始位置,则从i+1开始考虑,若[i+1,gas.length-1]区间内不出现curSum小于0的情况,注意:此时只考虑了半圈,说明在该区间内不出现新的起始位置,只考虑i+1位置就行。
但是,i+1只是有可能是正确的,因为它完全可能在另一半圈[0,i]累加求和中出现curSum小于0的情况。这时就要看totalSum,若小于0,说明没有起始位置,i+1作为起始位置也不行;若大于0,说明有起始位置,i+1可以作为起始位置。
for (int i=0;i<gas.length;i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {start = i + 1;curSum = 0;}
}
2. LeetCode 135. 分发糖果
题目链接:https://leetcode.cn/problems/candy/description/
文章链接:https://programmercarl.com/0135.分发糖果.html
视频链接:https://www.bilibili.com/video/BV1ev4y1r7wN

思路:
本题关键:处理好一边再处理另一边,不要两边想着一起兼顾。
采用两次贪心的策略:
1️⃣一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
局部最优:只要右边评分比左边大,右边的孩子就多一个糖果;
全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果。
2️⃣一次是从右到左遍历,只比较左边孩子评分比右边大的情况。
局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。
全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。
这样从局部最优推出了全局最优,即:相邻的孩子中,评分高的孩子获得更多的糖果。
解法:
class Solution {public int candy(int[] ratings) {int[] candy = new int[ratings.length];for (int i=0;i<candy.length;i++) {candy[i] = 1;}// 从前往后遍历 比较右孩子评分大于左孩子的场景for (int i=0;i<ratings.length-1;i++) {if (ratings[i] < ratings[i+1]) {candy[i+1] = (candy[i]+1);}}// 从后往前遍历 比较左孩子评分大于右孩子的场景for (int i=ratings.length-2;i>=0;i--) {if (ratings[i] > ratings[i+1]) {candy[i] = Math.max(candy[i],candy[i+1]+1);}}return Arrays.stream(candy).sum();}
}
3. LeetCode 860.柠檬水找零
题目链接:https://leetcode.cn/problems/lemonade-change/description/
文章链接:https://programmercarl.com/0860.柠檬水找零.html
视频链接:https://www.bilibili.com/video/BV12x4y1j7DD

思路:
本题关键:只需要维护三种金额的数量:5,10和20。
存在 如下三种情况:
情况一:账单是5,直接收下。
情况二:账单是10,消耗一个5,增加一个10
情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5
账单是20的情况,为什么要优先消耗一个10和一个5呢?
因为美元10只能给账单20找零,而美元5可以给账单10和账单20找零,美元5更万能!
贪心:
局部最优:遇到账单20,优先消耗美元10,完成本次找零。
全局最优:完成全部账单的找零。
class Solution {// public boolean lemonadeChange(int[] bills) {// if (bills[0] > 5) {// return false;// }// Map<String,Integer> map = new HashMap<>();// map.put("5",0);// map.put("10",0);// map.put("20",0);// for (int i=0;i<bills.length;i++) {// if (bills[i] == 5) {// map.put("5",map.get("5")+1);// } else if (bills[i] == 10) {// if (map.get("5") <= 0) {// return false;// } else {// map.put("5",map.get("5")-1);// }// map.put("10",map.get("10")+1);// } else if (bills[i] == 20) {// if (map.get("5") <= 0) {// return false;// } else if (map.get("10") <= 0 && map.get("5") < 3) {// return false;// } else if (map.get("10") > 0) {// map.put("10",map.get("10")-1);// map.put("5",map.get("5")-1);// } else if (map.get("5")>=3) {// map.put("5",map.get("5")-3);// }// map.put("20",map.get("20")+1);// }// }// return true;// }public boolean lemonadeChange(int[] bills) {if (bills[0] > 5) {return false;}Map<String,Integer> map = new HashMap<>();map.put("5",0);map.put("10",0);map.put("20",0);int num5 = 0;int num10 = 0;int num20 = 0;for (int i=0;i<bills.length;i++) {if (bills[i] == 5) {num5++;} else if (bills[i] == 10) {if (num5 <= 0) {return false;} else {num5--;}num10++;} else if (bills[i] == 20) {if (num10 > 0 && num5 > 0) {num10--;num5--;} else if (num5 >= 3) {num5 = num5 - 3;} else {return false;}num20++;}}return true;}
}
4. LeetCode 406.根据身高重建队列
题目链接:https://leetcode.cn/problems/queue-reconstruction-by-height/description/
文章链接:https://programmercarl.com/0406.根据身高重建队列.html
视频链接:https://www.bilibili.com/video/BV1EA411675Y

思路:
本题关键:本题有两个维度,h和k。确定一个维度,然后再按照另一个维度重新排列。
首先按照身高排序,然后优先按身高高的people的k来插入,后续插入节点即便插入到了已经插入节点的前边,也不会影响前面已经插入的节点,最终按照k的规则完成了队列。(后续插入的节点的身高始终低于前面已经插入的节点的身高,即便插入到前边,不影响前面已经插入节点的k值)
按照身高从大到小排序后:
局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优:最后都做完插入操作,整个队列满足题目队列属性
注意:按照身高排序时,若身高相同,则优先将k小的排在前面。
解法:
class Solution {public int[][] reconstructQueue(int[][] people) {// 1.先按照身高进行降序排序,然后按照k进行升序排序Arrays.sort(people,(a,b) -> {if (a[0] == b[0]) return a[1]-b[1];return b[0]-a[0];});LinkedList<int[]> queue = new LinkedList<>();// 2. 向前插入for (int[] p:people) {queue.add(p[1],p);}return queue.toArray(new int[people.length][]);}
}
相关文章:
代码随想录算法训练营第29天|LeetCode 134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列
1. LeetCode 134. 加油站 题目链接:https://leetcode.cn/problems/gas-station/description/ 文章链接:https://programmercarl.com/0134.加油站.html 视频链接:https://www.bilibili.com/video/BV1jA411r7WX 思路: 贪心ÿ…...
代理模式(大话设计模式)C/C++版本
代理模式 C #include <iostream> using namespace std;class Subject // Subject 定义了RealSubject和Proxy的共用接口..这样就在任何使用RealSubject的地方都可以使用Proxy { public:virtual void func(){cout << "Subject" << endl;} };class R…...
本人学习保存-macOS打开Navicat提示「“Navicat Premium”已损坏,无法打开。 你应该将它移到废纸篓。」的解决方法
新安装了macOS Ventura,打开Navicat Premium,发现会提示: “Navicat Premium”已损坏,无法打开。 你应该将它移到废纸篓。 遇到这种情况,千万别直接移到废纸篓,是有办法解决的。在这里记录一下解决方案。 …...
《Cross-Image Pixel Contrasting for Semantic Segmentation》论文解读
期刊:TPAMI 年份:2024 摘要 研究图像语义分割问题。目前的方法主要集中在通过专门设计的上下文聚合模块(如空洞卷积、神经注意力)或结构感知的优化目标(如iou样损失)挖掘"局部"上下文,即单个图像中像素之间的依赖关系。然而&…...
技术周总结 2024.07.08~07.14(算法,Python,Java,Scala,PHP)
文章目录 一、07.13 周六1.0)算法题:字符串中的单词反转1.1) 问题01:可靠性计算中的MTTR MTTF MTBF 分别指什么?他们之间有什么联系?MTTR (Mean Time to Repair)MTTF (Mean Time to Failure)MTBF (Mean Time Between F…...
UnityECS学习中问题及总结entityQuery.ToComponentDataArray和entityQuery.ToEntityArray区别
在Unity的ECS(Entity Component System)开发中,entityQuery.ToComponentDataArray<T>(Allocator.Temp) 和 entityQuery.ToEntityArray(Allocator.Temp) 是两种不同的方法,用于从实体查询中获取数据。除了泛型参数之外&#…...
[python]基于yolov10+gradio目标检测演示系统设计
【设计介绍】 YOLOv10结合Gradio实现目标检测系统设计是一个结合了最新目标检测技术和快速部署框架的项目。下面将详细介绍这一系统的设计和实现过程。 一、YOLOv10介绍 YOLOv10是YOLO(You Only Look Once)系列的最新版本,由清华大学的研究…...
浏览器开发者视角及CSS表达式选择元素
点击想要查看的接口,然后点击检查,便可以切换到该接口对应的html代码 如果F12不起作用的话,点击更多工具,然后选择开发者工具即可 ctrlF可以去查阅相关的CSS表达式选择元素 如果没有加#t1,那么表示的是选择所有的p 使用…...
GuLi商城-商品服务-API-品牌管理-统一异常处理
每个方法都加这段校验太麻烦了 准备做一个统一异常处理@ControllerAdvice 后台代码: package com.nanjing.gulimall.product.exception;import com.nanjing.common.exception.BizCodeEnum; import com.nanjing.common.utils.R; import lombok.extern.slf4j.Slf4j; import org…...
VUE+Spring Flux实现SSE长连接
VUE代码 // 初始化EventSourceinitEventSource(url) {const token getAccessToken();const eventSource new EventSourcePolyfill(url, {headers: {Authorization: Bearer ${token},tenant-id: getTenantId(),}});eventSource.onerror (e) > {console.log("SSE连接错…...
C#实现Winform程序右下角弹窗消息提示
前言 消息通知在应用程序中,是一种非常有用的功能,实现对一些重要信息、提醒或警告及时向用户展示。我们在使用软件时,通常会收到一种从桌面右下角弹出的(提示信息或广告)信息框。本文将介绍使用 C# 实现此种方式的信息…...
Java三剑客:封装、继承、多态的魔法世界
第一章:封装的艺术 —— 保护你的宝藏 案例分析:银行账户系统 想象一下,你正在构建一个银行账户系统。每个账户都有一个余额,这个余额需要受到严格的保护,不能被随意修改。我们可以通过封装来实现这一目标。 示例代…...
0145__Linux的capability
https://zhuanlan.zhihu.com/p/693896673 Linux的capability深入分析(1)_linux 设置进程capprm-CSDN博客 cap_init(3) - Linux manual page...
# Redis 入门到精通(一)数据类型(4)
Redis 入门到精通(一)数据类型(4) 一、redis 数据类型–sorted_set实现时效性任务管理 1、sorted_set 类型数据操作的注意事项 score 保存的数据存储空间是64位,如果是整数范围是-9007199254740992~9007199254740992…...
西邮计科嵌入式复习
西邮嵌入式复习 一、第一章复习二、第二章复习三、第三章复习四、第四章复习 一、第一章复习 二、第二章复习 三、第三章复习 四、第四章复习...
Java如何使用 HttpClientUtils 发起 HTTP 请求
Java如何使用 HttpClientUtils 发起 HTTP 请求 一、前言1.HttpClientUtils 类概览2.解析 HttpClientUtils 类3.使用 HttpClientUtils 类 一、前言 在现代的软件开发中,经常需要与远程服务器进行通信,例如获取数据或发送数据。Apache HttpClient 是一个流…...
无人机的工作原理
无人飞行器(UAV,即Unmanned Aerial Vehicle)的工作原理涉及多个复杂的系统和技术。以下是对各个系统和技术的详细介绍: 1. 飞行控制系统(FCS) 飞行控制系统是无人机的“大脑”,负责监控和调整…...
敏捷开发笔记(第10章节)--Liskov原则(LSP)
目录 1:PDF上传链接 10.1 Liskov替换原则(LSP) 10.2 一个违反LSP的简单例子 10.6 启发式规则和习惯用法 10.7 结论 1:PDF上传链接 【免费】敏捷软件开发(原则模式与实践)资源-CSDN文库 OCP背后的主要机制是抽象(abstraction…...
基于SSM的校园一卡通管理系统的设计与实现
摘 要 本报告全方位、深层次地阐述了校园一卡通管理系统从构思到落地的整个设计与实现历程。此系统凭借前沿的 SSM(Spring、Spring MVC、MyBatis)框架精心打造而成,旨在为学校构建一个兼具高效性、便利性与智能化的一卡通管理服务平台。 该系…...
新版Android Studio中设置gradle的JDK版本
旧版android studio 在旧版(具体哪个版本号之前搞不清了)中设置JDK版本在>File——>Project Structure——>SDK location——>Gradle Setting——>Gradle SDK 新版android studio 某次更新后发现SDK location下找不到Gradle Setting选项…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
JS红宝书笔记 - 3.3 变量
要定义变量,可以使用var操作符,后跟变量名 ES实现变量初始化,因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符,可以创建一个全局变量 如果需要定义…...
HTTPS证书一年多少钱?
HTTPS证书作为保障网站数据传输安全的重要工具,成为众多网站运营者的必备选择。然而,面对市场上种类繁多的HTTPS证书,其一年费用究竟是多少,又受哪些因素影响呢? 首先,HTTPS证书通常在PinTrust这样的专业平…...
