# 【LEETCODE】模拟面试-134-Gas Station

### 题目：

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.

### 分析：

This question is to find the start point where the car can complete a circuit.

Input: two arrays, one represents the gas at each station point, another one is cost when the car travels from point i to point i+1. **Output: **if the car can't finish a whole circuit, return -1, if yes, return the index of start point. Note: there maybe multiple solutions, but we just need one path.

The brute force method is that we can scan from 0 to last, each point will be considered as the start once. For each start, we will iterate all the following points in the circuit, and calculate the left gas. If the gas decreases below 0 during the process, this start point is failing, so we can move to next start point. If this start can complete the circuit, we can return its index, and no need to continue searching.

But how to optimize above method? We can reduce some repeated work. Take this data set as an example:

index:

0,

1,

2,

3,

4,

5,

6

gas:

3,

4,

3,

6,

7,

1,

2

cost:

2,

4,

5,

1,

5,

1,

3

Since we only care about the left gas at each point, we can firstly transform two arrays to one:

leftGas:

1,

0,

-2,

5,

2,

0,

-1

Suppose this, when we start from index=0, and we can move on till index=2, since the sum_leftGas here is 1, but we can't move to index=3. Then we can just ignore index=1,2 without considering them as start point, since they will be stuck at index_3 too.

And we continue from point index_3, it turns out all the left gas at each station can be >=0, so index_3 can be a start point.

This process is like a Queue: since we scan from 0 to 3, and 0,1,2 fails to be a start, so we pop them out, and continue from 3 to 4,5,6,0,1,2, till 3, a circuit finished.

But we can still optimize it. without pop 0,1,2 and add them again, we can just apply the structure Deque which can add and pop on both sides. Since the path will be a circuit, there's no need to delete any point, just add point on different sides, finally the points in de deque will combine a path.

So we start from 0, if the sum_gas will be >=0, we add next point on right side, otherwise, we add point on the left side.

### Java

```public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost){
//corner
if ( gas == null || cost == null || gas.length != cost.length )
return -1;

//core
int start = gas.length - 1;                     //用two pointer模拟deque，并不需要建立deque
int end = 0;

int gasLeftSum = gas[start] - cost[start];

while ( start > end ){

if ( gasLeftSum >= 0 ){                         //end开始并为加进来，所以先加，再右移
gasLeftSum += gas[end] - cost[end];
end++;
}else{
start--;
gasLeftSum += gas[start] - cost[start];     //start最开始已经被加上了，所以先左移，再加油
}
}

return  gasLeftSum >= 0 ? start : -1;
}
}```

0 条评论

## 相关文章

3444

### HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

3726

### 聊聊storm的GraphiteStormReporter

storm-core-1.2.2-sources.jar!/org/apache/storm/metrics2/reporters/GraphiteStormR...

1441

### 聊聊storm tuple的序列化

storm-2.0.0/storm-client/src/jvm/org/apache/storm/executor/ExecutorTransfer.java

884

### Gym 100952D&&2015 HIAST Collegiate Programming Contest D. Time to go back【杨辉三角预处理，组合数，dp】

D. Time to go back time limit per test：1 second memory limit per test：256 megaby...

2966

1271

### POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

3326

### HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2856

### HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

3334

### HDU 5877 2016大连网络赛 Weak Pair(树状数组，线段树，动态开点，启发式合并，可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

40210