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

目录134. 加油站题目描述题目例子解题思路135. 分发糖果题目描述题目例子解题思路860. 柠檬水找零 - 力扣LeetCode题目描述题目例子解题思路406. 根据身高重建队列 - 力扣LeetCode题目描述题目例子解题思路134. 加油站题目描述在一条环路上有n个加油站其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的的汽车从第i个加油站开往第i1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发开始时油箱为空。给定两个整数数组gas和cost如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回-1。如果存在解则保证它是唯一的。题目例子gas [1,2,3,4,5],cost [3,4,5,1,2]输出3从3号加油站出发获得4升汽油此时油箱有4升汽油开往四号加油站此时油箱有4-158升汽油开往零号加油站此时油箱有8-217升汽油开往一号加油站此时油箱有7-326升汽油开往二号加油站此时油箱有6-435升汽油开往三号加油站此时油箱有5-50升汽油正好回到三号加油站解题思路以下为暴力解法以每一个位置开始加油看能否到达起始点class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: for i in range(len(gas)): remain gas[i] - cost[i] index (i 1) % len(gas) #index为i时已经回到了起始站 while index ! i and remain 0: remain gas[index] - cost[index] index (index 1) % len(gas) #汽车在起始站并且剩余的油量大于等于0 if index i and remain 0: return i return -1局部最优从起始点到当前站点剩余油量大于0全局最优求出最后的其实站点题目中说明解的存在是唯一的为什么如果从起始点到当前站点时剩余油量小于0时起始站点就等于当前站点的下一个站点而不是从其实站点到当前站点的某一个站点对于起始点-----中间站点-----当前站点如果此时cursum 0那么cursum(区间一) cursum(区间二) cursum假设要取中间站点为起始点此时cursum(区间二) 0则cursum(区间一) 0按照我上面的描述此时会从中间站点1开始作为起始站点class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: start 0 cursum totalsum 0 for i in range(len(gas)): cursum gas[i] - cost[i] totalsum gas[i] - cost[i] if cursum 0: start i 1 cursum 0 return start if totalsum 0 else -1135. 分发糖果题目描述n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求给这些孩子分发糖果每个孩子至少分配到1个糖果。相邻两个孩子中评分更高的那个会获得更多的糖果。请你给每个孩子分发糖果计算并返回需要准备的最少糖果数目。题目例子ratings [1,0,2]输出5发[2,1,2]颗糖果ratings [1,2,2]输出4发[1,2,1]颗糖果解题思路这道题不能只从左到右 / 从右到左单次遍历解决因为每个孩子需要同时满足左边和右边的规则所以用两次遍历分别处理两个方向的规则最后取最大值保证所有条件都满足。举个栗子ratings [1,3,2,1]初始化[1,1,1,1]左-右[1,2,1,1]右-左[1,3,2,1]为什么左孩子比右孩子评分高时要从右到左呢如果上述例子按照顺序遍历的话就会变成[1,2,2,1]从左往右遍历只能保证当前比左边大无法保证当前比右边大左边孩子的糖果数此时依赖右边孩子的糖果数---先计算右边再计算左边class Solution: def candy(self, ratings: List[int]) - int: candy [1] * len(ratings) #右边孩子评分比左边孩子高 for i in range(1,len(candy)): if ratings[i] ratings[i-1]: candy[i] candy[i - 1] 1 #左边孩子评分比右边孩子高 for i in range(len(candy) - 2,-1,-1): if ratings[i] ratings[i1]: candy[i] max(candy[i 1]1,candy[i]) return sum(candy)860. 柠檬水找零 - 力扣LeetCode题目描述在柠檬水摊上每一杯柠檬水的售价为5美元。顾客排队购买你的产品按账单bills支付的顺序一次购买一杯。每位顾客只买一杯柠檬水然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付5美元。注意一开始你手头没有任何零钱。给你一个整数数组bills其中bills[i]是第i位顾客付的账。如果你能给每位顾客正确找零返回true否则返回false。题目例子bills [5,5,5,10,20]输出True从前三位顾客收到3张5元第四位顾客需要找零5元第五位顾客需要找零15元都够解题思路一共三种情况收到5元不用找零收到10元找5元收到20元找1张10元和1张五元或者找3张五元局部最优遇到20元优先消耗10元完成找零全局最优完成全部账单找零class Solution: def lemonadeChange(self, bills: List[int]) - bool: five 0 ten 0 for x in bills: if x 5: five 1 if x 10: if five 0: return False ten 1 five - 1 if x 20: if five 0 and ten 0: ten - 1 five - 1 elif five 3: five - 3 else: return False return True406. 根据身高重建队列 - 力扣LeetCode题目描述假设有打乱顺序的一群人站成一个队列数组people表示队列中一些人的属性不一定按顺序。每个people[i] [hi, ki]表示第i个人的身高为hi前面正好有ki个身高大于或等于hi的人。请你重新构造并返回输入数组people所表示的队列。返回的队列应该格式化为数组queue其中queue[j] [hj, kj]是队列中第j个人的属性queue[0]是排在队列前面的人。题目例子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 的人。解题思路局部最优优先按身高高的people的k来插入。插入操作过后的people满足队列属性全局最优最后都做完插入操作整个队列满足题目队列属性先把最高的人排好再把矮一点的人按要求的位置直接插进队列里。已经在队列里的人都比后来插入的人高 → 插入不会破坏已有的规则class Solution: def reconstructQueue(self, people: List[List[int]]) - List[List[int]]: #从高到低同一身高的按要求位置从小到大排好 people.sort(key lambda x:(-x[0],x[1])) que [] for x in people: #每个人直接插到下标 他的 k 值的位置 que.insert(x[1],x) return que