題目出處

134. Gas Station

難度

medium

個人範例程式碼

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

        if sum(gas) < sum(cost):
            return -1

        remain_gas = 0
        start_station = 0
        for i in range(len(gas)):
            remain_gas += gas[i]
            remain_gas -= cost[i]
            if remain_gas < 0:
                # change start station
                remain_gas = 0
                start_station = i+1

        return start_station

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

我們透過 0 不斷的 「+ gas[i]」，移動至下一個 station 「- cost[i]」，
當發現 remain_gas 小於 0 時，表示這個加油站適合當最後一站。

(用最後剩的 gas 回到此處。)

更改 start station 位置時， start_station 的位置改為「i+1」

input handling

如果 sum(gas) < sum(cost)，不可能走完全程。
反之，一定走得完全程，至少會有一個答案。 (題目也限制了，只會有一個答案)

Boundary conditions

用 for 控制來範圍

Reference

• 加油站 · Gas Station