Gas Station [leetcode] 的兩種解法

Gas Station [leetcode] 的兩種解法

由於gas總量大於cost總量時，一定可以繞所有城市一圈。

第一種解法：

假設一開始有足夠的油，從位置i出發，到位置k時剩余的油量為L(i,k)。

對任意的k，L(i,k)根據i的不同，只相差常數。

我們只需要找到最小的L(0, k)對應的k，k+1為所求。

代碼如下：

    int canCompleteCircuit(vector &gas, vector &cost) {
        int start = 0;
        int curGas = 0, minGas = 0, totalGas = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            int temp = gas[i] - cost[i];
            curGas += temp;
            totalGas += temp;
            if (minGas > curGas)
            {
                start = i + 1;
                minGas = curGas;
            }
        }
        if (totalGas >= 0) return start % gas.size();
        else return -1;
    }

如果L(i,k) < 0，則從i和k之間所有的位置都不能到k

所以從k+1的位置從0開始找

    int canCompleteCircuit(vector &gas, vector &cost) {
        int start = 0;
        int curGas = 0, totalGas = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            int temp = gas[i] - cost[i];
            curGas += temp;
            totalGas += temp;
            if (curGas < 0)
            {
                start = i + 1;
                curGas = 0;
            }
        }
        if (totalGas >= 0) return start % gas.size();
        else return -1;
    }