134. 加油站
“可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。” ----代码随想录
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:rest = []n = len(gas)for i in range(n):rest.append(gas[i]-cost[i])if sum(rest) < 0:return -1cur_sum = 0start = 0for i in range(n):cur_sum += rest[i]if cur_sum < 0:cur_sum = 0start = i+1# print('start=', start)if start>=n:return -1else:return start135. 分发糖果
记得拆分，从左往右和从右往左
“本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路” --代码随想录
class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)candy_l = [1] * ncandy_r = [1] * n# candy_l# candy_r[-1] = 1# from left to right, compare to the previous childfor i in range(1, n):if ratings[i] > ratings[i-1]:candy_l[i] = candy_l[i-1]+1# from right to left, compare to the next childfor i in range(n-1, 0, -1):if ratings[i] < ratings[i-1]:candy_r[i-1] = candy_r[i] + 1candy = []for i in range(n):candy.append(max(candy_l[i], candy_r[i]))# print('candy_l:', candy_l)# print('candy_r:', candy_r)# print('candy:', candy)result = sum(candy) return result860.柠檬水找零
class Solution:def lemonadeChange(self, bills: List[int]) -> bool:changes = {5: 0, 10: 0, 20: 0}for bill in bills:changes[bill] += 1if bill == 5:continueelif bill == 10:if changes[5] == 0:return Falsechanges[5] -= 1else:if changes[10] > 0 and changes[5] > 0:changes[5] -= 1changes[10] -= 1elif changes[5] >= 3:changes[5] -= 3else:return Falsereturn True406.根据身高重建队列
list的insert方法时间复杂度是O(n)。
要注意语言，尽量深耕一门语言。
class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key=lambda x: (-x[0], x[1])) # 第一个数从大到小排，第二个数从小到大排que = []for p in people:que.insert(p[1], p)return que
