代码随想录算法训练营第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选项…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
