【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;
    }
}