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 -1
cur_sum = 0
start = 0
for i in range(n):
cur_sum += rest[i]
if cur_sum < 0:
cur_sum = 0
start = i+1
# print('start=', start)
if start>=n:
return -1
else:
return start135. 分发糖果
记得拆分，从左往右和从右往左
“本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路” --代码随想录
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candy_l = [1] * n
candy_r = [1] * n
# candy_l
# candy_r[-1] = 1
# from left to right, compare to the previous child
for 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 child
for i in range(n-1, 0, -1):
if ratings[i] < ratings[i-1]:
candy_r[i-1] = candy_r[i] + 1
candy = []
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] += 1
if bill == 5:
continue
elif bill == 10:
if changes[5] == 0:
return False
changes[5] -= 1
else:
if changes[10] > 0 and changes[5] > 0:
changes[5] -= 1
changes[10] -= 1
elif changes[5] >= 3:
changes[5] -= 3
else:
return False
return True
406.根据身高重建队列
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