代码随想录算法训练营第二十九天| 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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2