leetcode每日一题—134.加油站

题目：
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

思路一：
设置一个remain值来判断，当前油量是否足够行驶到下一站。

解答一：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n=len(gas)
        remains=[0]*n
        for i in range(n):
            remains[i]=gas[i]-cost[i]
        print(remains)

        for i in range(n):
            m=n-1
            #在i号加油站加的油，足够汽车行驶到（i+1）号加油站
            if remains[i]>=0：
                #行驶到（i+1)%n 号加油站时，邮箱里剩余的油量
                remain=remains[i]
                j=i+1
                while m:
                    #油量不足以支撑汽车行驶到下一站
                    if remains[j%n]+remain<0:
                        break
                    #油量足以支撑汽车行驶到下一站，更新剩余油量值
                    else:
                        remain+=remains[j%n]
                        j+=1
                    m-=1
                #若汽车可以回到原点，即i号加油站
                if m==0:
                    return i             
        return -1

思路二：

start和end设置得很精妙！

解答二:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        end = 0
        start = len(gas) - 1
        SUM = gas[start] - cost[start]
        while start > end:
            if SUM >= 0 :
                SUM += gas[end] - cost[end]
                end += 1
            else:
                start -= 1
                SUM += gas[start] - cost[start]
        return start if SUM>=0 else -1