leetcode solution Gas Station
z
 2018-03-03 20:54:44  

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int currentGas = 0;
        int balance = 0;
        int start = 0;
        for(int i=0; i<gas.length; i++){
            currentGas +=  gas[i] - cost[i];
            if(currentGas < 0){
                balance += currentGas;
                currentGas = 0;
                start = i+1;
            }
        }
        balance += currentGas;
        if(balance < 0){
            return -1;
        }
        else{
            return start;
        }
    }
}
  • 遍历一遍数组，currentGas 保存从start 点开始到当前第i-1个点剩下的gas.如果小于0，则说明从start 点开始能到达 i-1 但是不能到达i 。即说明start 到i 中的任意一个节点都不能作为起始点。
    • 可以利用反证法。假设start到i中存在一个点c，使得c能作为起始点，那么c一定能到达i，又由于start能到达c（因为start能到达i-1），start就能到达i，矛盾。
  • balance 中保存从0开始到最后一个起始点位置gas-cost之和。在循环外再加上一个currentGas，即可得到从0到n中，gas和和cost和。balance小于0，即说明不存在这样一个start point。