## Monday, November 11, 2013

### [LeetCode] Gas Station, Solution

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.

[Thoughts]

diff[i] = gas[i] – cost[i]  0<=i <n

1. 能否在环上绕一圈？

2. 如果能，这个起点在哪里？

sum[i,j] = ∑diff[k] where i<=k<j

[Code]
1:  class Solution {
2:  public:
3:      int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
4:          vector<int> diff(gas.size());
5:          for(int i =0; i< gas.size(); ++i)
6:          {
7:              diff[i] = gas[i] - cost[i];
8:          }
9:
10:          int leftGas=0, sum =0, startnode=0;
11:          for(int i =0; i<gas.size(); ++i)
12:          {
13:              leftGas += diff[i];
14:              sum += diff[i];
15:              if(sum <0) //只要小于0就不可能是解
16:              {
17:                  startnode = i+1;
18:                  sum=0;
19:              }
20:          }
21:          if(leftGas <0)
22:              return -1;
23:          else
24:              return startnode;
25:      }
26:  };