題目

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1

1
2
3
4
5
6
7
8
9
10
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2

1
2
3
4
5
6
7
8
9
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104
  • The input is generated such that the answer is unique.

解釋題目

題目會給兩個 list，一個是 gas[n] 另一個是 cost[n]，gas 的 index 跟 value 代表每個站點可以新增的油量；cost 的 index 跟 value 代表每個站點會消耗的油量。題目要求出的是從哪個站點 (也就是 index)出發，可以順利跑完全程。假設從 0 站跑到 1 站的時候，0 站的油量要扣掉 0 站會消耗的油量，到第 1 站時油量要是大於 0 的。如果油量 < 0，那這站就不能是起點。如果有解的話，題目設定是唯一解。

思路

  1. 這題最重要的是總油量要大於總汽油消耗量，也就是 sum(gas) >= sum(cost)，不過在寫程式時，可以用 for 迴圈可以遍歷每個 gas[i] - cost[i] ，這樣就可以計算 總油量 - 總油消耗量是否大於 0。

  2. 這題另一個重要的概念就是 greedy 的解法，假設總油量是夠的，那就一定會有解，只是不知道從哪站開始出發，根據這樣的邏輯，只要這一站行不通，就換下一站。所以，即使前面有些站的油量不夠，後面站的油量也會補回來，因為整體的油量是夠的。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canCompleteCircuit(gas, cost):
    total_tank = 0
    curr_tank = 0
    start_index = 0

    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total_tank = total_tank + diff
        curr_tank = curr_tank + diff

        if curr_tank < 0:
            start_index = i + 1
            curr_tank = 0

    return start_index if total_tank >= 0 else -1