Question:
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.
Solution:
1 class Solution { 2 public: 3 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { 4 int sum=0; 5 int index; 6 bool flag=false; 7 int count=0; 8 for(int i=0;count<=gas.size();i++) 9 { 10 if(flag==false) 11 index=i; 12 flag=true; 13 if(i<gas.size()) 14 sum+=gas[i]-cost[i]; 15 else 16 sum+=gas[i-gas.size()]-cost[i-gas.size()]; 17 count++; 18 if(sum<0) 19 { 20 flag=false; 21 sum=0; 22 count=0; 23 } 24 if(count==gas.size()) return index; 25 if(i>=2*gas.size()-1) {return -1;} 26 } 27 } 28 };
原文：http://www.cnblogs.com/riden/p/4631587.html