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)),则有以下公式成立:
[sum_{i = x}^{y-1} gas[i] lt sum_{i = x}^{y-1} cost[i]
]
[sum_{i = x}^j gas[i] >= sum_{i = x}^{j}cost[i], x le j le y - 2
]
第一个式子表示无法到达站点(y),第二个式子表明可以到达(y)之前的所有站点。现在,考虑任意一个位于(x,y)之间的加油站(z),考察从该加油站出发能否到达站点(y),也就是要判断(sum_{i = z}^{y-1} gas[i])和(sum_{i = z}^{y - 1} cost[i])。根据上面的式子我们可以得到:
[egin{equation}
egin{aligned}
sum_{i = z}^{y - 1} gas[i] &= sum_{i = x}^{y - 1} gas[i] - sum_{i = x}^{z - 1} gas[i]\
& lt sum_{i = z}^{y - 1} cost[i] - sum_{i = x}^{z - 1} gas[i] \
& lt sum_{i = z}^{y - 1} cost[i] - sum_{i = x}^{z - 1} cost[i]\
& = sum_{i = z}^{y - 1} cost[i]
end{aligned}
end{equation}
]
以上公式说明从(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;
}
};