[LeetCode] 134. Gas Station

想到了提前判断和小于0的情况，懒得写，果然被阴间用例10万个加油站坑了。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #1
        n = len(gas)
        if n ==1:
            if gas[0] >= cost[0]:
                return 0
            else:
                return -1
        #-1
        startpoint =[gas[x] - cost[x] for x in range(n)]
        if all(element < 0 for element in startpoint) or sum(startpoint) <0:
            return -1
        #else
        ret = -1
        for i, element in enumerate(startpoint):
            if element >= 0:
                total = 0
                temp =startpoint[i:]+ startpoint[:i]
                for i2, element2 in enumerate(temp):
                    total += element2
                    if total <0:
                        break
                    if i2 == n-1:
                        ret = i
                        return ret
        return ret

然后发现更阴间的99999个0的测试用例,Pycharm调试都崩溃了。。。
跳过了0的情况，题目说明可能的解是唯一的，所以0不影响结果。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #1
        n = len(gas)
        if n ==1:
            if gas[0] >= cost[0]:
                return 0
            else:
                return -1
        #-1
        startpoint =[gas[x] - cost[x] for x in range(n)]
        if all(element < 0 for element in startpoint) or sum(startpoint) <0:
            return -1
        #else
        ret = -1
        for i, element in enumerate(startpoint):
            if element > 0:
                total = 0
                temp =startpoint[i:]+ startpoint[:i]
                for i2, element2 in enumerate(temp):
                    if element2 ==0:
                        continue
                    total += element2
                    if total <0:
                        break
                    if i2 == n-1:
                        ret = i
                        return ret
        return ret

然后就遇到99995个1。。。换个思路解题。
不需要考虑已经走过的加油站，只需要维护一个总的燃油量，如果循环结束总量大于0，就说明已经走过的加油站可以在循环的后半程走完。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #else
        total_gas, curr_gas = 0, 0
        start_point = 0
        for i, element in enumerate(gas):
            curr_gas += element - cost[i]
            total_gas += element - cost[i]
            if curr_gas < 0:
                start_point = i + 1
                curr_gas = 0

        return start_point if total_gas >=0 else -1

近期做的最辛苦的一次，一开始思路被带偏了。