代码随想录算法训练营第二十九天| 134. 加油站 135. 分发糖果 860.柠檬水找零 406.根据身高重建队列

2024-08-29 00:52
文章标签 算法 随想录 代码 队列 训练营 第二十九 分发 重建 135 糖果 134 找零 加油站 柠檬水 身高 406 860

本文主要是介绍代码随想录算法训练营第二十九天| 134. 加油站 135. 分发糖果 860.柠檬水找零 406.根据身高重建队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

134. 加油站

题目：

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

思路：

要解决这个问题，可以使用贪心算法。

核心思想是：如果从某个加油站出发，无法到达下一个加油站，那么从这个加油站及之前的任意一个加油站出发都不可能完成一周的环路。

因此，我们可以贪心地选择下一个加油站作为新的起点，直到找到一个可以完成一周的起点。

具体步骤：

  1. 初始化 total_tank 和 current_tank 为 0，这两个变量分别表示整个环路上的总剩余油量和当前段的剩余油量。同时，初始化起始加油站 start_station 为 0。

  2. 遍历每个加油站 i，计算从加油站 i 开始到达下一个加油站后的剩余油量 current_tank += gas[i] - cost[i]。

  3. 如果 current_tank 小于 0，说明从当前 start_station 到加油站 i 这段路上的油量不足以支持到达下一个加油站，这意味着从 start_station 出发不可能完成环路。此时我们将 start_station 设置为 i+1，并将 current_tank 重置为 0。同时，total_tank 累加 current_tank 的值。

  4. 最后，如果 total_tank 大于等于 0，则说明存在一个可行的起始加油站 start_station，否则返回 -1 表示无法完成环路。

上代码：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int total_tank = 0, current_tank = 0;int start_station = 0;for (int i = 0; i < gas.size(); ++i) {total_tank += gas[i] - cost[i];current_tank += gas[i] - cost[i];if (current_tank < 0) {start_station = i + 1;current_tank = 0;}}return total_tank >= 0 ? start_station : -1;}
};

135. 分发糖果

题目：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

思路：

解决这个问题的贪心思路是通过两次遍历来确保每个孩子获得的糖果数满足条件：

  1. 第一次遍历：从左到右遍历数组，确保每个孩子比左边评分低的孩子获得更多的糖果。
  2. 第二次遍历：从右到左遍历数组，确保每个孩子比右边评分低的孩子获得更多的糖果，同时尽量减少糖果的分配。

贪心算法的具体步骤：

  1. 初始化：

    • 创建一个数组 candies，其中每个元素初始化为 1，表示每个孩子至少分到一个糖果。

  2. 从左到右遍历：

    • 从左到右遍历 ratings 数组。如果当前孩子的评分比前一个孩子高，那么 candies[i] = candies[i-1] + 1，确保当前孩子的糖果比前一个孩子多。

  3. 从右到左遍历：

    • 从右到左遍历 ratings 数组。如果当前孩子的评分比下一个孩子高，并且 candies[i] <= candies[i+1]，那么 candies[i] = candies[i+1] + 1，确保当前孩子的糖果比后一个孩子多。
    • 最后，将 candies 数组中的所有元素相加，即为最少需要的糖果数量。

上代码：

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> candies(n, 1);  // 每个孩子至少得到一个糖果// 从左到右遍历for (int i = 1; i < n; ++i) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历for (int i = n - 2; i >= 0; --i) {if (ratings[i] > ratings[i + 1]) {candies[i] = max(candies[i], candies[i + 1] + 1);}}// 计算最少糖果数目int totalCandies = 0;for (int candy : candies) {totalCandies += candy;}return totalCandies;}
};

860.柠檬水找零

题目：

在柠檬水摊上，每一杯柠檬水的售价为 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 <= 105
  • bills[i] 不是 5 就是 10 或是 20 

思路：

这个问题可以用贪心算法来解决。

贪心的核心思想是：在处理每个顾客的找零时，尽量优先使用大面额的钞票，以便保留更多的小面额钞票来应对后续的找零需求。

贪心算法的具体步骤：

  1. 初始化：

    • 使用两个变量 five 和 ten 分别记录手中持有的 5 美元和 10 美元的数量。

  2. 遍历每位顾客的支付情况：

    • 如果顾客支付 5 美元，直接将 five 加 1，因为不需要找零。
    • 如果顾客支付 10 美元，首先检查是否有 5 美元的钞票，如果有，给顾客找零 5 美元，然后将 five 减 1，同时将 ten 加 1；如果没有 5 美元的钞票，返回 false，因为无法找零。
    • 如果顾客支付 20 美元，优先尝试使用一张 10 美元和一张 5 美元的钞票来找零，如果有，将 ten 减 1 和 five 减 1；如果没有 10 美元的钞票，再尝试使用三张 5 美元的钞票来找零，如果也不够，返回 false。

  3. 遍历完成后：

    • 如果整个过程中都能够成功找零，则返回 true，否则返回 false。

上代码：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (int bill : bills) {if (bill == 5) {five++;} else if (bill == 10) {if (five > 0) {five--;ten++;} else {return false;}} else if (bill == 20) {if (ten > 0 && five > 0) {ten--;five--;} else if (five >= 3) {five -= 3;} else {return false;}}}return true;}
};

406.根据身高重建队列

题目：

假设有打乱顺序的一群人站成一个队列，数组 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 <= 106
  • 0 <= ki < people.length
  • 题目数据确保队列可以被重建

思路：

根据题目，我们可以得出：

  1. 身高高的人对身高矮的人没有影响：因为我们希望每个人前面有恰好 k 个身高大于或等于他的人。因此，先安排身高较高的人，对于身高较矮的人的位置不会产生影响。

  2. 贪心策略：我们可以先按身高从高到低排序，如果身高相同，则按 k 值从小到大排序。这样，先安排身高高的、k 值小的人员，然后再插入身高较矮的人员，这样可以确保在插入时不会影响之前已经放置的人员的顺序。

贪心算法的步骤：

  1. 排序：

    • 将 people 数组按以下规则进行排序：
      • 首先按身高 h 降序排列。
      • 如果身高相同，则按 k 值升序排列。

  2. 插入：

    • 依次按照排序后的顺序将每个人插入到结果队列中。对于每一个人 people[i] = [hi, ki]，将他插入到队列的第 ki 个位置。

    这种插入操作可以保证最终结果满足每个人前面有恰好 k 个比他高或与他同高的人。

上代码：

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {// 先排序，按身高从高到低排序，若身高相同则按 k 值从小到大排序sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);});vector<vector<int>> queue;// 依次插入每个人到队列的指定位置for (const auto& person : people) {queue.insert(queue.begin() + person[1], person);}return queue;}
};

这篇关于代码随想录算法训练营第二十九天| 134. 加油站 135. 分发糖果 860.柠檬水找零 406.根据身高重建队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1116377。

相关文章

Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
Java中调用数据库存储过程的示例代码

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
MySQL数据库的内嵌函数和联合查询实例代码

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面：本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN
阅读更多...
Java实现自定义table宽高的示例代码

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格（JTable）作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码
阅读更多...
Go语言代码格式化的技巧分享

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具：gofmt 与 go fmt（一）
阅读更多...
HTML5实现的移动端购物车自动结算功能示例代码

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.
阅读更多...
基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码，该代码实现了图片的旋转（90度和180度）以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中，
阅读更多...
Python如何去除图片干扰代码示例

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,：本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声（像素值正态分布扰动）2. 椒盐噪声（随机黑白像素点）3. 复杂噪声（如伪
阅读更多...
Java Spring ApplicationEvent 代码示例解析

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念（发布-订阅/观察者模式）、代码实现（事件定义、发布、监听）及高级应用（异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2