2014.2.26 00:34
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:
The problem asks you to find a position where you start at, and can finish your trip through all the stations without running out of gas.
Aparrently there is an O(n^2) solution. You do an O(n) scan for every position and get the correct result, as well as an TLE.
Let‘s think about a situation: you started at position i, and unluckily ran out of gas at position j. Then would it be possible to start at some position k between i and j and successfully finish the trip? The answer must be no, otherwise an O(n) algorithm cannot be achieved.
When you‘re travelling, your gas g >= 0. When you run out of gas, g < 0. So you must‘ve spent more than you get. You stared at i and stopped at j, that means g[i]~g[j - 1] are all >= 0, while g[j] < 0.
Let‘s suppose you start at some position k between i and j. If you can successfully pass position j, we have:
1. g‘[j] = g[j] - g[k] >= 0, suppose you can reach j if you start at k.
2. for all k in [i, j - 1], g[k] >= 0, because you reached all positions before j.
3. g[j] < 0, you failed to reach j if you start at i.
4. g[j] - g[k] >= 0, a negative must be smaller than a non-negative, contradiction.
Thus we know the hypothesis above cannot hold, i.e. if you failed at position [j] when you started at position [i], you‘ll sure fail in the positions between them. Start searching from [j + 1] instead.
That conclusion expains why it‘s a linear algorithm, as well as online.
Total time complexity is O(n). Space complexity is O(1).
Accepted code:
1 // 1WA, 1AC, O(n) online solution. 2 class Solution { 3 public: 4 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 5 int total_sum; 6 int current_sum; 7 int i; 8 int n; 9 int start_pos; 10 11 n = (int)gas.size(); 12 if (n == 0) { 13 return -1; 14 } 15 16 total_sum = current_sum = 0; 17 start_pos = 0; 18 for (i = 0; i < n; ++i) { 19 total_sum += gas[i] - cost[i]; 20 current_sum += gas[i] - cost[i]; 21 if (current_sum < 0) { 22 // you cannot finish the trip 23 // because you used us the gasoline here 24 // need a new start from next station 25 start_pos = (i + 1) % n; 26 current_sum = 0; 27 } 28 } 29 30 if (total_sum < 0) { 31 // impossible to finish the trip 32 return -1; 33 } else { 34 return start_pos; 35 } 36 } 37 };
原文：http://www.cnblogs.com/zhuli19901106/p/3568203.html