题目

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

解法

这道题分两步来做，第一步先确定是否能周游一圈，第二步在找从哪个加油站开始。

确定能否周游一圈

首先给出一个断言：如果gas数组元素之和大于等于cost数组元素之和，那么必然能周游一圈。证明很简单，可以这样想象下，加油站的高度为0，加油站的油高度为gas,cost代表两个加油站之间的坑深度，且油的流向为同一个方向，那么当gas之和大于等于cost之和的话，最终动态平衡后整体油面高度>=0，那么必然能周游一圈。否则不能。

从哪个加油站开始

一开始没看到题目的note，感觉可以从多个加油站开始。note提示题目有唯一解，我想如果能找到环中最大连续序列的和的话，那么就能找到其实点，但是找环中的最大连续感觉比找数组中最大连续序列和（见http://blog.csdn.net/xhu_eternalcc/article/details/24880013）要难，就直接蛮力找的：如果从某个加油站能向前遍历N步（加油站的个数），那么就是从这个加油站开始，需要进行如下优化:

det[i]=gas[i]-cost[i]

sum为从第i个加油站开始，向前遍历到某加油站时的总剩油量

1）起始加油站的det[i]>=0

2)  当从第i个加油站开始，向前step步，到达第(i+step)%N个加油站,sum<0时，这时在探测第x= i+1 至(i+step)%N个加油站能否作为开始点时，可以直接求得从加油站x到(i+step)%N 的总剩油量sum，详见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int sum=0;
int *det=new (std::nothrow)int[gas.size()];
for(std::vector<int>::size_type i=0;i<gas.size();++i){
det[i]=gas[i]-cost[i];
sum+=det[i];
}
if(sum<0){
delete [] det;
return -1;
}
int step=0;
for(std::vector<int>::size_type i=0;i<gas.size();++i){
if(step>0){//i-1加油站向前走step步后总油量开始<0
--step;
if(det[i]<0){
sum-=det[i];
continue;
}else if(sum<0){
sum-=det[i];
continue;
}
}else{
if(det[i]<0)
continue;
sum=det[i];
}
while(sum>=0&&step<gas.size()){
++step;
sum+=det[(step+i)%gas.size()];
}
if(step==gas.size()){
delete [] det;
return i;
}
else
sum-=det[i];
}
}
};

最后

以上就是甜美花生最近收集整理的关于LeetCode之Gas Station --环形加油站周游题目解法代码的全部内容，更多相关LeetCode之Gas内容请搜索靠谱客的其他文章。