python实现leetcode之134. 加油站

解题思路

1.计算每一站到下一站的盈余油量
2.如果如果总盈余量小于0，从任何节点起步都不足以跑一圈
如果总盈余量大于0，总有一个点是可以的
3.寻找一个起点可以维持到下一个站台的站，然后开始考核
如果走完一圈，就是答案

134. 加油站

代码

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        delta = [g-c for g, c in zip(gas, cost)]  # 每一站到下一站的盈余油量
        if sum(delta) < 0: return -1  # 从任何节点起步都不足以跑一圈
        # 如果总盈余量大于0，总有一个点是可以的
        for i in range(len(delta)):  # 寻找一个起点
            S = 0
            if delta[i] < 0: continue
            else:  # 找到第一个可以维持到下一个站台的站，然后开始考核
                S = delta[i]
                pt = next_idx(i, len(delta))
                while pt != i:
                    S += delta[pt]
                    if S < 0: break  # 从i开始不行
                    pt = next_idx(pt, len(delta))
                if pt == i:  # 找到啦
                    return i


def next_idx(idx, limit):
    return (idx + 1) % limit