LeetCode 134 加油站

https://leetcode-cn.com/problems/gas-station/

法一 直接模拟

从头到尾遍历每个加油站，检查以该加油站为起点，最终能否绕行一圈。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sz = gas.size();
        for (int start = 0; start < sz; ++start) {
            if (gas[start] < cost[start]) continue;
            int v = gas[start];         // 剩余汽油量
            int j = (start + 1) % sz;   // 指向下一个要到达的站点
            while (j != start) {
                // 到达站点j并加油后的剩余汽油量
                v = v - cost[(j - 1 + sz) % sz] + gas[j];
                // 如果无法达到下一个（j+1）个站点
                if (v < cost[j]) break;
                j = (j + 1) % sz;
            }
            if (j == start) return start;
        }

        return -1;
    }
};

法二 一次遍历

我们尝试对上面的法一进行加速。假设从站点\(x\)出发，每经过一个加油站就加一次油，第一个无法到达的站点是\(y\)（力扣官方题解上应该是有误，如果第一个无法到达的站点是\(y\)，那么下面公式的上标只能取到\(y-1\)，而不是\(y\)），则有以下公式成立：

第一个式子表示无法到达站点\(y\)，第二个式子表明可以到达\(y\)之前的所有站点。现在，考虑任意一个位于\(x,y\)之间的加油站\(z\)，考察从该加油站出发能否到达站点\(y\)，也就是要判断\(\sum_{i = z}^{y-1} gas[i]\)和\(\sum_{i = z}^{y - 1} cost[i]\)。根据上面的式子我们可以得到：

以上公式说明从\(x, y\)之间的任何一个站点出发，都无法到达站点\(y\)。既然如此，我们首先检查第0个加油站，并试图找到第一个无法到达的加油站\(z\)。如果能找到，下一次就从加油站\(z + 1\)开始检查。最终，我们只遍历了原数组一次。时间复杂度降到了\(O(N)\)

代码如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sz = gas.size();
        int start = 0;
        while (start < sz) {
            // 从起始位置开始往前移动
            int skip = 0;
            int sumOfGas = 0, sumOfCost = 0;
            while (skip < sz) {
                int z = (start + skip) % sz;
                sumOfGas += gas[z];
                sumOfCost += cost[z];
                // 如果找到了第一个无法到达的站点x则退出
                if (sumOfCost > sumOfGas) break;
                ++skip;
            }

            // 如果刚好绕了一圈回到了起点则返回起点位置下标
            if (skip == sz) return start;
            // 否则将起始位置调整为x + 1
            start += (skip + 1);
        }

        return -1;
    }
};

LeetCode 134 加油站

原文：https://www.cnblogs.com/wallace-lai/p/13999114.html