- 29.3%

https://leetcode.com/problems/gas-station/

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.

具体原理及贪心算法还需要再思考

方法一：

我的代码实现:

Oct 18，2017

1 | class Solution { |

My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?

I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

1 | class Solution { |

my code:

1 | class Solution { |

#### cpp

https://discuss.leetcode.com/topic/1344/share-some-of-my-ideas

Share some of my ideas.

I have thought for a long time and got two ideas:

- If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.)
- If the total number of gas is bigger than the total number of cost. There must be a solution.

(Should I prove them?)

Here is my solution based on those ideas:

1 | class Solution { |

My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?

I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

1 | class Solution { |

Proof of “if total gas is greater than total cost, there is a solution”. C++

We prove the following statement.

If sum of all gas[i]-cost[i] is greater than or equal to 0, then there is a start position you can travel the whole circle.

Let i be the index such that the the partial sum

1 | gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] |

is the smallest, then the start position should be start=i+1 ( start=0 if i=n-1). Consider any other partial sum, for example,

1 | gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]+gas[i+1]-cost[i+1] |

Since gas[0]-cost[0]+gas[1]-cost[1]+…+gas[i]-cost[i] is the smallest, we must have

1 | gas[i+1]-cost[i+1]>=0 |

in order for gas[0]-cost[0]+gas[1]-cost[1]+…+gas[i]-cost[i]+gas[i+1]-cost[i+1] to be greater.

The same reasoning gives that

1 | gas[i+1]-cost[i+1]>=0 |

What about for the partial sums that wraps around?

1 | gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1] |

The last inequality is due to the assumption that the entire sum of gas[k]-cost[k] is greater than or equal to 0.

So we have that all the partial sums

1 | gas[i+1]-cost[i+1]>=0, |

Thus i+1 is the position to start. Coding using this reasoning is as follows:

1 | class Solution { |

Fully-commented O(n) C++ solution enabled by a single observation of mine

1 | class Solution { |

https://discuss.leetcode.com/topic/29487/my-one-pass-solution

My one pass solution.

1 | class Solution { |

The idea is simple.

- Whenever the sum is negative, reset it and let the car start from next point.
- In the mean time, add up all of the left gas to total. If it’s negative finally, return -1 since it’s impossible to finish.
- If it’s non-negative, return the last point saved in res;

6ms, September 20, 2016

1 | class Solution { |

#### python

https://discuss.leetcode.com/topic/27760/possibly-the-most-easiest-approach-o-n-one-variable-python

55ms, 32.89%, September 20, 2016

解析：sum（gas）>= sum（gas），能保证存在一个位置，可以作为起点。

如果从位置position开始进行旅行，这一段到某一点没有油了，则以position为起点的这一段肯定不存在作为起点的位置，否则走不完这一段，所以postion设为从下一个位置开始，其他的类似。

my code的思想类似，不过是移动起点和终点的位置，如果小于0，起点向前移动，如果大于0，则起点向后移动。

1 | class Solution(object): |

my code

1 | class Solution(object): |

#### java

https://discuss.leetcode.com/topic/7247/my-o-n-time-o-1-extra-space-solution

My O(N) time, O(1) extra space solution.

1 | public class Solution { |

Straightforward Java Linear Solution with O(1) space, explanation and Math proof

The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That’s what the first loop does.

If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station.

1 | public int canCompleteCircuit(int[] gas, int[] cost) { |

https://discuss.leetcode.com/topic/25990/simple-o-n-java-solution-with-comments

1ms, September 20, 2016

1 | public class Solution { |