[LeetCode Python3] 134. Gas Station+暴力遍历+简单剪枝134. Gas Station

90 阅读 0 评论 60 点赞

我是靠谱客的博主缓慢云朵，这篇文章主要介绍[LeetCode Python3] 134. Gas Station+暴力遍历+简单剪枝134. Gas Station，现在分享给大家，希望可以做个参考。

134. Gas Station

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
size = len(gas)
for index in range(size):
#遍历所有站，只要当前油站的油量大于该站到下一站要耗的油量时才有可能作为起点
if gas[index] >= cost[index]:
tank = gas[index]
# 将起点油站的油加入油箱
flag = True
for i in range(1, size): # 从起点的下一站开始遍历
tank = tank - cost[(index+i-1) % size] + gas[(index+i) % size] # 油箱中的油减去上一段消耗的再加上本站的油量
if tank < cost[(index+i) % size]:
# 若此时油箱中的油小于下一段路程要消耗的油则不能到达，即该index不能作为起点
flag = False
break
if flag:
return index
return -1