【Day25】LeetCode：134. 加油站，135. 分发糖果，860. 柠檬水找零，406. 根据身高重建队列

文章目录LeetCode134. 加油站思路解答LeetCode135. 分发糖果思路解答LeetCode860. 柠檬水找零思路解答LeetCode406. 根据身高重建队列思路解答LeetCode134. 加油站https://leetcode.cn/problems/gas-station/思路首先计算每个加油站的净收益得到全程的总剩余油量1如果为负数则总油量不足以支撑全程返回 -1。2如果不为负数则一定存在一个可行的起点。初始化cur_gas 0表示当前累计的剩余油量start 0表示当前试探的起点。从i 0开始遍历每个加油站将diff[i]累加到cur_gas1如果cur_gas始终非负说明从当前起点出发能顺利到达当前位置。2如果cur_gas 0意味着从起点到当前位置i这一段路程无法完成。此时将起点设为i 1并将cur_gas重置为 0继续向后试探。【原因说明此时起点start到i的累计净收益为负。那么对于任意一个介于start和i之间的点k从k出发到i的累计净收益也必然为负。因为从start到k的累计净收益是非负的否则在更早之前就会重置起点。】解答classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])-int:diff[]# 记录每个加油站到下一个加油站剩余油的的净含量nlen(gas)gas_remain0foriinrange(n):gas_remaingas[i]-cost[i]diff.append(gas[i]-cost[i])ifgas_remain0:# 如果所有加油站油小于总耗油量则无法成环return-1cur_gas0start0foriinrange(n):cur_gasdiff[i]ifcur_gas0:starti1cur_gas0returnstartLeetCode135. 分发糖果https://leetcode.cn/problems/candy/description/思路通过两次遍历来满足条件。每个孩子先发 1 颗糖果。从左向右遍历确保当右边孩子评分高于左边时右边孩子的糖果数大于左边。当ratings[i] ratings[i-1]则candies[i] candies[i-1] 1。从右向左遍历确保当左边孩子评分高于右边时左边孩子的糖果数大于右边。当ratings[i] ratings[i1]则candies[i] max(candies[i], candies[i1] 1)。解答classSolution:defcandy(self,ratings:List[int])-int:nlen(ratings)candies[1]*n# 每个孩子至少1颗糖果# 从左到右foriinrange(1,n):ifratings[i]ratings[i-1]:candies[i]candies[i-1]1# 从右到左foriinrange(n-2,-1,-1):ifratings[i]ratings[i1]:candies[i]max(candies[i],candies[i1]1)returnsum(candies)LeetCode860. 柠檬水找零https://leetcode.cn/problems/lemonade-change/思路尽可能用 10 找零。如果找零时 5 不足则无法找零。解答classSolution:deflemonadeChange(self,bills:List[int])-bool:five0ten0forbillinbills:ifbill5:# 收5不用找零five1elifbill10:# 收10只能用5找零five-1ten1else:# 收20可以用5、10找零优先用10iften0:five-1ten-1else:five-3iffive0:# 改顾客无法找零returnFalsereturnTrueLeetCode406. 根据身高重建队列https://leetcode.cn/problems/queue-reconstruction-by-height/思路先将people按照身高降序、k升序排列。遍历排序后的people对于每个人[h, k]将其插入到queue的索引k处。因为此时queue中已有的所有人身高都 当前人的身高所以当前人插入到位置 k 后他前面正好有 k 个人身高都 他。解答classSolution:defreconstructQueue(self,people:List[List[int]])-List[List[int]]:people.sort(keylambdax:(-x[0],x[1]))# 身高降序k升序queue[]forpinpeople:# 插入到索引 p[1] 的位置queue.insert(p[1],p)returnqueue