day29|leetcode 134. 加油站 , 135. 分发糖果 ,860.柠檬水找零 , 406.根据身高重建队列

ops/2024/11/28 14:52:04/

8.加油站

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

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

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -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 可为起始索引。

首先很快能想到的点就是:gas总和如果小于cost总和那么肯定无解

贪心算法体现在:

使用curSum不断累加记录gas[i]-cost[i],如果curSum<0那么这个区间中的任何一个加油站点都不可能作为起点,curSum清零,从i+1重新开始累加,直到循环遍历完

期间使用totalSum记录所有的gas-cost值,最后判断totalSum与0的关系来得出是否有解

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int startIndex = 0;for(int i=0;i<gas.size();i++){curSum+=gas[i]-cost[i];//curSum用于暂时记录总数,主要目的是寻找起始点totalSum+=gas[i]-cost[i];//total记录的是总数if(curSum<0){curSum = 0;//清零//从i+1的位置开始startIndex = i+1;}}if(totalSum<0)return -1;//说明不可能达到 return startIndex;}};

9.分发糖果

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

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

  • 每个孩子至少分配到 1 个糖果。

  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

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

解读要求:

(1)相邻的小孩两两比较,评分高的拥有更多糖果

(2)每个小孩至少一个糖果

两边一起顾及就会顾此失彼,面对两个维度的问题就该先处理一个维度再处理另一个维度

由于第一条,可以从左往右遍历比较左孩子先分一遍糖果

然后再从右往左遍历比较右孩子再分糖果,但是这里由于遍历左孩子的基础---->右孩子分的糖果candy[i]=max(candy[i],candy[i]+1);取较大值,而不是直接叠加,这样才能满足评分高的孩子的糖果数比相邻两侧评分较低的孩子的糖果多

class Solution {
public:int candy(vector<int>& ratings) {vector<int>candy(ratings.size(),1);//每个小孩先都分一块for(int i=1;i<ratings.size();i++){if(ratings[i]>ratings[i-1]){candy[i]=candy[i-1]+1;}}//从左往右遍历先初始分一遍for(int j=ratings.size()-2;j>=0;j--){if(ratings[j]>ratings[j+1]){candy[j]=max(candy[j],candy[j+1]+1);}}int result = 0;for(int a:candy)result+=a;return result;}
};

10.柠檬水找零

在柠檬水摊上,每一杯柠檬水的售价为 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。

发现

(1)5元直接收下

(2)10元要找一张5元

(3)20元可以找一张10元和一张5元或者直接找三张5元

5元最万能,要省着用,前面两种情况都操作不了,只能对20元的情况使用贪心算法

优先找10和5,实在不行再找三张五,这样才能保证我们尽可能给更多的顾客找零

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0;int ten = 0;for (int bill : bills) {if (bill == 5) // 直接收下{five++;} else if (bill == 10) // 找5{ten++;if (five > 0)five--;elsereturn false;  // 找不了} else if (bill == 20) // 优先消耗10和5{if (ten > 0 && five > 0) {ten--;five--;} else if (five >= 3) // 没有10{five -= 3;} else { // 找不了零return false;}}}return true;}
};

11.根据身高重建队列

假设有打乱顺序的一群人站成一个队列,数组 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]] 是重新构造后的队列。

与分糖果思想类似!

两边一起顾及就会顾此失彼,面对两个维度的问题就该先处理一个维度再处理另一个维度

如果按照k从小到大排,很容易出现k没排对且也不满足前面有>=k个高个子的要求

所以采取将身高从高到低进行排序,让高个子都排在前面,肯定能满足前面正好 有 ki 个身高大于或等于 hi 的人的要求

身高相同的就要k小的放前面

class Solution {static bool cmp(vector<int>&a,vector<int>&b){if(a[0]==b[0])return a[1]<b[1];//如果身高相同,那么k小的放前面为truereturn a[0]>b[0];//身高不相同,高的放前面为true}
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),cmp);vector<vector<int>>queue;for(int j=0;j<people.size();j++){int position=people[j][1];//取出people数组中第j个元素queue.insert(queue.begin() + position, people[j]);}return  queue;}
};

ps:今天比前几天难很多!


http://www.ppmy.cn/ops/137381.html

相关文章

【原创】springboot+vue高校勤工助学管理系统设计与实现

个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交给天意。 研究背景&#xff1a; 首…

实时数据开发 | Flink反压机制原因、影响及解决方案

今天是很忙碌的一天哦&#xff0c;有两个业务在催着验收&#xff0c;终于21&#xff1a;45卡点交上去了。 明早再修修补补一下应该就可以开始做实时方面的需求了&#xff0c;小紧张&#xff0c; 今天同事在同步会上讲这块业务的数据流时就提到了checkpoint和savepoint还有流处理…

【前端】JavaScript中的字面量概念与应用详解

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: 前端 文章目录 &#x1f4af;前言&#x1f4af;字面量1. 数字字面量2. 字符串字面量3. 布尔字面量4. 空值字面量&#xff08;null&#xff09;5. 对象字面量6. 数组字面量7. 正则表达式字面量8. 特殊值字面量9. 函数字…

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

docker安装mysql

1.拉取mysql镜像 docker pull mysql:5.7 2.启动mysql容器 docker run -d -e MYSQL_ROOT_PASSWORD123456 -e MYSQL_TCP_PORT3307 -p 3307:3307 -v /SDXL/wjz/docker_mysql_log:/var/log/mysql -v /SDXL/wjz/docker_mysql_data:/var/lib/mysql -v /SDXL/wjz/docker_mysql_conf:/e…

「Mac玩转仓颉内测版32」基础篇12 - Cangjie中的变量操作与类型管理

本篇将深入探讨 Cangjie 编程语言中的变量操作与类型管理&#xff0c;涵盖变量的定义、作用域、类型推断、常量、变量遮蔽、类型转换等方面的知识。通过这些概念的学习&#xff0c;开发者将更好地理解和灵活掌握变量的使用与管理技巧。 关键词 变量定义类型推断常量变量作用域…

一个简单的ASP.NET 一致性返回工具库

本文主要介绍了 Sang.AspNetCore.CommonLibraries 这个 ASP.NET 通用库&#xff0c;它目前提供了一致性返回和简单提示页面的功能&#xff0c;旨在简化开发工作&#xff0c;提高代码的复用性和可维护性。 1. 介绍 Sang.AspNetCore.CommonLibraries 是一个为 ASP.NET Core 提供…

后端并发编程操作简述 Java高并发程序设计 六类并发容器 七种线程池 四种阻塞队列

目录 并发集合 1. ConcurrentHashMap&#xff1a; 2. CopyOnWriteArrayList&#xff1a; 3. CopyOnWriteArraySet&#xff1a; 4. BlockingQueue系列&#xff1a; 5. ConcurrentSkipListMap 和 ConcurrentSkipListSet&#xff1a; 6. ConcurrentLinkedDeque&#xff1a;…