首页 > 代码库 > 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