gas station

gas station

Not hard

Tank can start at every position in the cycle, but each step it must maintain the gas >= 0. We call gas[i]-cost[i] = delta[i]. Tank must start at where delta[start] >= 0. Then, use a pointer named end to go around. if the gas in tank less than zero, tank should not start during[start,end].Try to start at end+1, iterate. if end<=start, and remaining gas less than zero, there is no start point.

 1 class Solution {
 2 public:
 3     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 4         int l = gas.size();
 5         if ( l != cost.size() ) {
 6             return -1;
 7         }
 8         if ( l == 0 ) {
 9             return -1;
10         }
11         int start = 0;
12         int sum = 0;
13         int end = 0;
14         while( start < l ) {
15             if ( gas[start] < cost[start] ) {
16                 start++;
17             } else {
18                 sum = gas[start]-cost[start];
19                 end = (start+1)%l;
20                 while ( end != start && sum >= 0 ) {
21                     sum += gas[end]-cost[end];
22                     end = (end+1)%l;
23                 }
24                 if ( sum >= 0 ) {
25                     return start;
26                 } else {
27                     if ( end <= start ) {
28                         return -1;
29                     } else {
30                         start = end;
31                     }
32                 }
33             }
34         }
35         return -1;
36     }
37 };

Loading Disqus comments...
Table of Contents