134. Gas Station

  • 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = gas.size()-1, end = 0;
int sum = gas[start] - cost[start];
while(start>end){
if(sum>=0){
sum += gas[end] - cost[end];
end++;
}else{
start--;
sum += gas[start] - cost[start];
}
}
return sum>=0 ? start : -1;
}
};

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

int start = gas.size()-1;
int end = 0;
int sum = gas[start] - cost[start]; // 注意此处初值的赋值
while (start > end) {
if (sum >= 0) {
sum += gas[end] - cost[end];
++end;
}
else {
--start;
sum += gas[start] - cost[start];
}
}
return sum >= 0 ? start : -1;
}
};

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size(), m = cost.size();
if(n!=m || m==n && m==0) return -1;
int start = n-1, end = 0;
int cur_gas = gas[start]-cost[start];
while(end <= start){
if(cur_gas>=0){
cur_gas += gas[end] - cost[end];
end++;
}
else{
start--;
cur_gas += gas[start] - cost[start];
}
}
return cur_gas>=0?start:-1;
}
};

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:

  1. 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.)
  2. 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
2
3
4
5
6
7
8
9
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int start(0),total(0),tank(0);
//if car fails at 'start', record the next station
for(int i=0;i<gas.size();i++) if((tank=tank+gas[i]-cost[i])<0) {start=i+1;total+=tank;tank=0;}
return (total+tank<0)? -1:start;
}
};

https://discuss.leetcode.com/topic/5088/my-ac-is-o-1-space-o-n-running-time-solution-does-anybody-have-posted-this-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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

int start = gas.size()-1;
int end = 0;
int sum = gas[start] - cost[start];
while (start > end) {
if (sum >= 0) {
sum += gas[end] - cost[end];
++end;
}
else {
--start;
sum += gas[start] - cost[start];
}
}
return sum >= 0 ? start : -1;
}
};

https://discuss.leetcode.com/topic/39755/proof-of-if-total-gas-is-greater-than-total-cost-there-is-a-solution-c

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
2
3
4
gas[i+1]-cost[i+1]>=0
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0
.......
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0

What about for the partial sums that wraps around?

1
2
3
4
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
>=
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
>=0

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
2
3
4
5
6
gas[i+1]-cost[i+1]>=0,
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0,
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0,
...
gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1] + gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j]>=0,
...

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int total(0), subsum(INT_MAX), start(0);
for(int i = 0; i < n; ++i){
total += gas[i] - cost[i];
if(total < subsum) {
subsum = total;
start = i + 1;
}
}
return (total < 0) ? -1 : (start%n);
}
};

https://discuss.leetcode.com/topic/8860/fully-commented-o-n-c-solution-enabled-by-a-single-observation-of-mine

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int i, j, n = gas.size();

/*
* If start from i, stop before station x -> no station k from i + 1 to x - 1 can reach x.
* Bcoz if so, i can reach k and k can reach x, then i reaches x. Contradiction.
* Thus i can jump directly to x instead of i + 1, bringing complexity from O(n^2) to O(n).
*/
// start from station i
for (i = 0; i < n; i += j) {
int gas_left = 0;
// forward j stations
for (j = 1; j <= n; j++) {
int k = (i + j - 1) % n;
gas_left += gas[k] - cost[k];
if (gas_left < 0)
break;
}
if (j > n)
return i;
}

return -1;
}
};

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

My one pass solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int size=gas.size();
int sum=0;
int res=0;
int total=0;
for(int i=0; i<size; ++i){
sum+=gas[i]-cost[i];
if(sum<0){
total+=sum;
sum=0;
res=i+1;
}
}
total+=sum;
return total<0?-1:res;
}};

The idea is simple.

  1. Whenever the sum is negative, reset it and let the car start from next point.
  2. 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.
  3. If it’s non-negative, return the last point saved in res;

https://discuss.leetcode.com/topic/5088/my-ac-is-o-1-space-o-n-running-time-solution-does-anybody-have-posted-this-solution

6ms, September 20, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = gas.size() - 1;
int end = 0;
int sum = gas[start] - cost[start];
while(start > end){
if(sum >= 0){
sum += gas[end] - cost[end];
++end;
}
else{
--start;
sum += gas[start] - cost[start];
}
}
return sum >= 0 ? start : -1;
}
};

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
if len(gas) == 0 or len(cost) == 0 or sum(gas) < sum(cost):
return -1
position = 0
balance = 0
for i in range(len(gas)):
balance += gas[i] - cost[i]
if balance < 0:
balance = 0
position = i+1
return position


my code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
start, end = len(gas)-1, 0
cur = gas[start]-cost[start]
while end<start:
if cur<0:
start -= 1
cur += gas[start] - cost[start]
else:
cur += gas[end] - cost[end]
end += 1
return start if cur>=0 else -1

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i = 0; i < gas.length; i++) {
gas[i] -= cost[i];
}
int sum = 0;
int result = 0;
int n = gas.length;
for(int i = 0; i < n * 2 - 1; i++) {
sum += gas[i % n];
if(sum < 0) {
result = i + 1;
if(result >= n) {
return -1;
}
sum = 0;
}
}
return result;
}

https://discuss.leetcode.com/topic/25289/straightforward-java-linear-solution-with-o-1-space-explanation-and-math-proof

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int canCompleteCircuit(int[] gas, int[] cost) {
int tank = 0;
for(int i = 0; i < gas.length; i++)
tank += gas[i] - cost[i];
if(tank < 0)
return - 1;

int start = 0;
int accumulate = 0;
for(int i = 0; i < gas.length; i++){
int curGain = gas[i] - cost[i];
if(accumulate + curGain < 0){
start = i + 1;
accumulate = 0;
}
else accumulate += curGain;
}

return start;
}

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

1ms, September 20, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, index = 0;
for(int i=0; i<cost.length; i++){
int cur = gas[i] - cost[i];
tank += cur;
if(tank<0){
index = i+1;
tank = 0;
}
total += cur;
}
return total < 0 ? -1:index;
}
}
谢谢你,可爱的朋友。