Gas Station （环形加油站）

题目：有n个加油站首尾相连成一个圆，已知每个加油站的油量，以及从第i个加油站到第i+1个加油站需消耗的油量，问：能否开车从某个加油站出发，循环一圈又回到起点，如果可以返回出发的起点（车的邮箱容量是无限的）。

此题目来自于leetcode，其原文地址为：https://oj.leetcode.com/problems/gas-station/

此解决方法为自己原创，目前在网上也没有搜索到类似的。

算法时间复杂度为O(n)，每个加油站只访问一次。 和网上看到的优雅方案（附后）不差上下。呵呵，纯粹个人感觉。

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;
}
};

算法思路为：

1.  任取一个加油站，作为起点start，然后往前一直开，直到油不够。未能到达之站，记为end。

2.  此时，说明start不适合作起点站。则偿试以start的前面一站作为起点，并更新start，再次偿试，看能否开到站点end。

3.   如果不能开到站点end，说明此站也不合适，继续步骤2.

4.   如果能开到站点end，则继续往前开。直到油不够，并更新end指向此未到之站。继续步骤2.

5.   重复下去，直到start和end相遇。

在实现在，我将最后一个站点作为start，可以省去一个取模超作，即end前进可以简单的写作++end,而start后退可以简单的写作—start。

省去了写成 end = (end + 1)%N;  start =(start + N -1)%N;

此处贴上在网上看到的优雅方案，供大家比较。

public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int N = gas.length, startIndex = -1;
int sum = 0, total = 0;
for(int i = 0; i < N; i++){
sum += (gas[i] - cost[i]);
total += (gas[i] - cost[i]);
if(sum < 0){
startIndex = i;
sum = 0;
}
}
return total >= 0 ? startIndex + 1 : -1;
}
}

注，此方案为Java语言实现，故接口与上C++实现略有不同。

要透彻理解上面两个算法，最好的方法是先理解下面这道证明题:

一个环形轨道上有n个加油站，所有加油站的油量总和正好够车跑一圈。证明，总能找到其中一个加油站，使得初始时油箱为空的汽车从这里出发，能够顺利环行一圈回到起点。
答案：总存在一个加油站，仅用它的油就足够跑到下一个加油站（否则所有加油站的油量加起来将 不够全程）。把下一个加油站的所有油都提前搬到这个加油站来，并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方，不断合并加油站，直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。
另一种证明方法：先让汽车油箱里装好足够多的油，随便从哪个加油站出发试跑一圈。车每到一个加油站时，记录此时油箱里剩下的油量，然后把那个加油站的油全部装上。试跑完一圈后，检查刚才路上到哪个加油站时剩的油量最少，那么空着油箱从那里出发显然一定能跑完全程。

该证明题摘抄自：http://www.matrix67.com/blog/archives/2671

实际上，

前一个算法，是基于证明方法一（合并加油站）上实现的。当然对其作了一点引申。

后一个算法，是基于证明方法二（即找到途中最小剩油量的加站）。当然也是作了一点引申。

作者： 静水流风

最后

以上就是尊敬白开水为你收集整理的Gas Station （环形加油站）的全部内容，希望文章能够帮你解决Gas Station （环形加油站）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。