首页 > 代码库 > Gas Station

Gas Station

https://oj.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.

解题思路:

两个结论:1.如果gas的总和<cost的总和,是车无论从哪一点出发,都无法走过全程。2.假设车从i出发,j是第一个无法到达的点,则从i-j间的任意点出发,都无法抵达j。(为什么?)

i无法抵达j,即gas[i-j]的总和 - cost[i-j-i]的总和<0。考虑从i+1出发,因为j是第一个无法到达的店,所以i是可以到达i+1的,所以gas[i]>=cost[i],所以总数减去这个正数,更加为负,所以i+1更加无法到达。同样,考虑i+2出发,因为i可以到达i+2,所以gas[i]+gas[i+1]>=cost[i]+cost[i+1],同样整体减去这个正数,更加为负数,以此类推,得到证明。

但是必须注意,这个结论反之不成立。即,从i出发可以到达j,那么i-j之间的点,不见得都能到j。

第一个结论可以用来判断什么时候return -1。第二个结论用来写程序。

两层循环,外层i表示出发点,j用来走,长度为length。如果小于零,则i直接跳到j+1。所以实际上的时间复杂度接近O(n)。

public class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        for (int i = 0; i < gas.length; ){            //int start = i;            int sum = 0;            int success = 1;            for(int j = 0; j < gas.length; j++){                sum += gas[(i + j) % gas.length] - cost[(i + j) % gas.length];                if(sum < 0){                    success = 0;                    i = i + j + 1;                    break;                }            }            if(success == 1){                return i;            }        }        return -1;    }}

定义:

diff[i] = gas[i] – cost[i]  0<=i <n 

sum[i,j] = ∑diff[k] where i<=k<j 

再改进,上面的算法中,从i出发,到n-1,然后套圈(overlap),从0到i-1。这里,套圈计算从0到i-1是没有必要的(为什么?)。

要证明这个,我们无非是要证明,仅仅计算sum[i, n]>=0是无效的。有可能sum[i, n]>=0,然而sum[i, n] + sum[0, k] < 0,这里0<k<i。即i出发能到n,却回不到i,在k点就终止了。真正的点是后面的一个j,i<j<n作为起点,有sum[j, n]>=0,也能绕一圈回到j。这是不可能的,事实上j也到不了k(如何证明?)。

假设从i出发,第一个到不了的点为k,这里0<k<i - 1。那么根据结论2,把i到n-1到0到k想象成一个线段,j在i到k之间,j更加到不了k了。所以这样的j点不存在。

从i出发不能套圈回到i,则意味着sum[i, n] + sum[0, i] < 0。考虑从i出发,那么意味着sum[0, i]<0,为什么?根据第二个结论显而易见。这里对于一个>i的j,由于i可以到j,所以sum[i,j]>=0。上述不等式可以改为sum[i, j] + sum[j, n] + sum[0, i] <0。考虑从j出发,去掉前面的sum[i,j]>=0,不等式更加小于0了。所以j出发根本不可能绕一圈。得证。

上面引用的证明是错误的,为什么?因为i出发无法绕圈回到i,并不意味着sum[i, j] + sum[j, n] + sum[0, i] <0,这是整体都无解的条件,真正无法达到的点可能是任意一个k。

这是一个简单却要想一想的结论,即因为有唯一解,从i出发,可以走到n,他就一定能回到i。因为i后的j点,更加不可能走到n,也能回到j。如果i不可以,则因该return -1,无解。

从而考虑将套圈的过程省去,就免去了内循环。不断的计算sum[i,j] ,一旦<0,从新的起点i+1开始计算。到n-1结束。不要套圈,免去了第二个控制n长度的游标。

public class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int start = 0;        int sum = 0;        int sumGas = 0;        int sumCost = 0;        for (int i = 0; i < gas.length; i++){            sumGas += gas[i];            sumCost += cost[i];            sum += gas[i] - cost[i];            if(sum < 0){                sum = 0;                start = i + 1;            }        }        if(sumGas < sumCost){            return -1;        }else{            return start;        }    }}

再次思考,上述结论实际是一个非常简单的结论。由于有唯一解,假设解为i。那么从i前任意点k都是无法无法到达i的,即sum[k,i-1] (0<=k<i-1) 肯定是小于0的,否则k出发也可以。而且i后面的任意点k,sum[i,k]>0 (i<=k<n-1),否则i都到不了k。 

这个题目其实很神奇,将diff[i]看作一个array,它还类似于一个maxlength subarray,即求最长子字符串的问题,可以用动态规划的方法求解。其实就是在0到n之间,找到第一个以n结尾的>=的连续子序列。这里dp的模型是始终以n结束,遍历开头。 而maxlength subarray的每个dp的模型是遍历结尾。

Gas Station