134. 加油站

class Solution:
 def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:
 if sum(cost) sum(gas):return -1
 n len(cost)
 for i in range(n): 
 tank 0
 for j in range(n):
 k (i j) % n 
 tank gas[k] - cost[k]
 if tank 0:break
 else: 
 return i
 return -1

如果从某个 start 开始到当前 i 油不够了 说明 start i 不可达 后面的总油量一定足够 所以从下一个 i 1 开始找下去 一定能找到符合条件的起点。

class Solution:
 def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: 
 if sum(gas) - sum(cost) 0: return -1 
 n, tank, start len(cost), 0, 0 # tank 记录油箱中的油量 start 记录起点
 for i in range(n):
 tank gas[i] - cost[i];
 # 如果油箱中油量小于 0 则从下一个加油站重新开始 说明无法从 0 走到 i。
 if tank 0: 
 tank 0
 start i 1
 return start 

class Solution:
 def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int: 
 n len(cost)
 tank total start 0
 for i in range(n): 
 tank gas[i] - cost[i] 
 if tank 0:
 start i 1
 total tank # 汇总 最后还得 tank 
 tank 0
 return start if tank total 0 else -1