# 134 - Gas Station

思考過程記錄

Greedy 演算法一

一開始，會想嘗試用最直覺的 Greedy 演算法來解，稍微觀察一下題目，發現有兩個重點：

1. 如果出發 station 的 gas 就比 cost 少，那就不可能成行，所以排除從這些 station 出發

2. 如果出發 station 的 gas-cost 最多，表示從這個 station 出發會能夠讓一開始擁有的資源最大化

綜合以上兩點，可以想出一個最直覺的演算法：從資源最多的 station 出發，如果能走回出發站，那就回傳出發站 index，如果不行就回傳 -1。實作出來的程式碼如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // Find the max diff station
        int maxGasStation, maxDiff = INT_MIN;
        for(int i=0; i<gas.size(); i++) {
            if(gas[i] - cost[i] > maxDiff) {
                maxDiff = gas[i] - cost[i];
                maxGasStation = i;
            }
        }

        // Simulate the traveling process
        int tank = 0;
        for(int i=maxGasStation; i<gas.size(); i++) {
            tank += gas[i];
            tank -= cost[i];
            if(tank < 0) return -1;
        }

        for(int i=0; i<maxGasStation; i++) {
            tank += gas[i];
            tank -= cost[i];       
            if(tank < 0) return -1;
        }

        return maxGasStation;
    }
};

// idea: always start from max diff station, if that station cannot work, then return -1

可惜的是這演算法有涵蓋不到的情況，比如下例：

gas: [5,8,2,8] cost: [6,5,6,6]

我們的演算法會 output -1，因為會從 index 1 出發，然後在 index 2 的地方把耗光。但如果是從 index 3 出發，那就可以走回來，不過也不用太氣餒，因為以上的演算法已經可以讓 24/31 test cases passed 了，我們只需要繼續改進即可。

Greedy 演算法二

既然剛剛我們會死在提早碰到 index 2 這個大魔王 station，那另一個想法就是，我們想辦法讓 gas-cost 最不足的 station 擺在最後，看前面累積的所有 gas 能否應付這關。畢竟如果要能走完一圈，那表示走完一圈，gas-cost 至少要 >= 0，如果連還還沒走到 gas-cost 最不足的 station 都不能滿足 gas-cost >= 0，那就不用走魔王關了。

實作出來的程式碼如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // Find the min gas-cost  station
        int minGasStation, minDiff = INT_MAX;
        for(int i=0; i<gas.size(); i++) {
            if(gas[i] - cost[i] <= minDiff) {
                minDiff = gas[i] - cost[i];
                minGasStation = i;
            }
        }

        cout << minGasStation << endl;

        // Simulate the traveling process
        int tank = 0;
        for(int i=minGasStation+1; i<gas.size(); i++) {
            tank += gas[i];
            tank -= cost[i];

            cout << "station: " << i << ", tank: " << tank << endl;

            if(tank < 0) return -1;
        }

        for(int i=0; i<=minGasStation; i++) {
            tank += gas[i];
            tank -= cost[i];

            cout << "station: " << i << ", tank: " << tank << endl;

            if(tank < 0) return -1;
        }

        return minGasStation+1;
    }
};

不過這個演算法還是會掛在另外的 case：

[5,1,2,3,4] [4,4,1,5,1]

我們的演算法會從 index 2 開始，但在 index 3 的地方就會沒油。但如果從 index 4 開始，就可以走得完。而這個 case 卻可以用 greedy 演算法一解決XD

解法一 - 用 one pass 的方法模擬從不同 station 出發的剩餘油量是否足夠

Leetcode 提供的 solution 實在是寫得太難懂了，還好後來看到一個想法比較相近的妙解 - https://leetcode.com/problems/gas-station/discuss/42565/My-AC-is-O(1)-space-O(n)-running-time-solution.-Does-anybody-have-posted-this-solution

趕快記一下方法：

The basic idea is every time we start from a station, we go as far as possible by increasing end until remaining gas is less than 0. If 'end' finally hits start we know we can travel around from 'start'. If we haven't traveled around, we know we cannot start from this station. Then we check the station before our start station if we can start from this station. Repeat until we have checked all stations.

Note there is a little trick that every time we try to find the next start station, we always to back to extend the distance from start to end so that we can check all stations on the circuit. Otherwise, if we move start forward to decrease the distance from start to end, we are likely to end up with only checking part of the circuit. Another trick is we start from the end of the array so as to avoid some corner cases.

程式碼如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = gas.size()-1;
        int end = 0;
        int sum = gas[start]-cost[start];

        while(start > end) {
            if(sum >= 0) {
                sum += gas[end]-cost[end];
                end++;
            }
            else {
                start--;
                sum += gas[start]-cost[start];
            }
        }

        return sum >= 0 ? start : -1 ;
    }
};