LeetCode 134. Gas Station [Medium] [C++] 解題筆記

這題給定兩個矩陣 gas 與 cost 分別表示在一個環狀的道路上在第 ith 個位置有 gas[i] 的汽油，而 cost[i] 表示從第 ith 個位置移動到第 (i+1)th 個位置所需要耗費的汽油量。假設有一台車子有無限的容量可以裝汽油，那摸從哪個位置開始移動能夠走完這個環狀道路一圈並保持在每個位置的時候汽油都是夠用的？

EX:

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.

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.

想法:

    這題除了暴力法外(O(n^2))還有一個小trick可以達到 O(n)的複雜度，關鍵就是

"如果以 i 為起點, 到第 j 點時汽油不夠 => 表示 i~j 都不可能存在起點"，因為以 i~j 中的點作為起點的話只要走到 j 汽油就會不夠

理解這點之後就可以發現，我們只需要從頭遍歷一次，然後當在某個位置 i 發現目前累積的 gas 少於 cost 時就將起點射為下一個位置(i+1)。

只要 total 的 gas[i] - cost[i] >= 0，就保證至少會有一個解。

完整程式碼:

/* brute-force O(n^2) solution */
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (int i = 0; i < gas.size(); i++) {
            int j = i;
            int cnt = 0;
            int tank = 0;
            while (cnt < gas.size()) {
                tank += gas[j] - cost[j];
                //cout<<tank<<endl;
                if (tank < 0) { break; }
                j = (j + 1) % gas.size();
                cnt++;
            }
            //cout<<cnt<<endl;
            if (tank >= 0) {
                return i;
            }
        }
        return -1;
    }
};
/* O(n) solution */
/* 如果以 i 為起點, 到第 j 點時汽油不夠 => 表示 i~j 都不可能存在起點 */
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank = 0;
        int total = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return (total < 0)? -1 : start;
    }
};