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

134. 加油站

leetcode 134. 加油站
代码随想录

暴力会超时，但是在面试的过程中，没有其他解法的时候，可以把暴力写好

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:# 暴力# if sum(gas) < sum(cost):#     return -1# for i in range(len(gas)):#     # 以i为起点，模拟一圈#     rest = gas[i] - cost[i]#     index= (i + 1) % len(gas)#     while rest > 0 and index != i:#         rest += gas[index] - cost[index]#         index= (index + 1) % len(gas)#     if rest >= 0 and index == i:#         return i# return -1cur_sum = 0total_sum = 0start_index = 0for i in range(len(gas)):cur_sum += gas[i] - cost[i]total_sum += gas[i] - cost[i]if cur_sum < 0:start_index = i + 1cur_sum = 0if total_sum < 0:return -1return start_index

135. 分发糖果

leetcode 135. 分发糖果
代码随想录

第二遍扫描的时候，忘了要保证另外一边的条件（需要取max(candy_list[i+1] + 1, candy_list[i]) ）。

class Solution:def candy(self, ratings: List[int]) -> int:# 扫描两遍candy_list = [1] * len(ratings)# 先满足右边评分高的比左边多for i in range(1, len(ratings), 1):if ratings[i] > ratings[i-1]:candy_list[i] = candy_list[i-1] + 1# 然后从后往前，再满足左边评分高的比右边多for i in range(len(ratings)-2, -1, -1):if ratings[i] > ratings[i+1]:# candy_list[i] = candy_list[i+1] + 1  # 如果改变这个值不满足比左边的大，不要改变candy_list[i] = max(candy_list[i+1] + 1, candy_list[i]) return sum(candy_list)

860.柠檬水找零

leetcode 860.柠檬水找零
代码随想录

要考虑周全，比如找零15的时候，如果没有十块，还可以用三个五块。

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:cur_change = 0# 需要记录10，5各有几张recored = [0] * 2 # 0:5, 1: 10for i in range(len(bills)):cur_pay = bills[i]if cur_pay == 5:recored[0] += 1elif cur_pay == 10:recored[0] -= 1if recored[0] < 0:return Falserecored[1] += 1elif cur_pay == 20:recored[0] -= 1if recored[1] == 0:recored[0] -= 2else:recored[1] -= 1if recored[0] < 0 or recored[1] < 0:return Falsereturn True

406.根据身高重建队列

leetcode 406.根据身高重建队列
代码随想录

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:# 身高的降序，k的升序，这样就一定可以保证在身高内肯定是满足的# 然后遍历排序好的list，再按照k插入就行了，# 为什么一定行？# 因为遍历到某一个元素的时候# 在同一身高内，后面的k比他的大，插入不影响，因为天然就在他后面# 身高比他矮的人插入任何位置都不会影响他的结果people.sort(key=lambda x: (-x[0],x[1]))que = []for p in people:que.insert(p[1], p)return que