面试150 加油站

思路

此题，我们从贪心算法的角度进行思考。通过计算净消耗，如果总的净消耗小于0，说明无论如何都不能环路行驶一周。我们通过定义一个start起点，通过遍历数组计算净消耗，如果净消耗小于0，重新置0，start更改为下一个坐标，然后重新计算。最后返回start

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:total=0for i in range(len(gas)):total+=gas[i]-cost[i]if total<0:return -1start=0sum=0for i in range(len(gas)):sum+=gas[i]-cost[i]if sum<0:sum=0start=i+1return start