Monday, November 24, 2014

[LeetCode] 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.

思路:

这题要想清楚不容易,尽管想清楚后代码写起来很简单。

I.  显然当gas[i]<cost[i]时,i不能作为起点。

II. 当对所有加油站求和:sum(gas[i] - cost[i]) <0时,无法环绕一圈。反之,则一定能环绕一圈。

问题是如果可以环绕一圈,如何找起点?

性质1. 对于任意一个加油站i,假如从i出发可以环绕一圈,则i一定可以到达任何一个加油站。显而易见。

性质2. 如果这样的i是唯一的,则必然不存在j!=i, 从j出发可以到达i。

反证法:如果存在这样的j,则必然存在j->i->i的路径,而这个路径会覆盖j->j一周的路径。那么j也将是一个符合条件的起点。与唯一解的限制条件矛盾。

性质3. 假如i是最后的解,则由1可知,从0 ~ i-1出发无法达到i。而从i出发可以到达i+1 ~ n-1。

结合以上三条性质,得出解决的思路:

0. 如果对所有加油站的sum(gas[i] - cost[i])<0,则无解。否则进入1。

1. 从0开始计算sum(gas[i] - cost[i]),当遇到i1使sum<0时,说明从0出发无法到达i1。根据性质1,0不是起始点。而由于从0出发已经到达了1 ~ i1-1。根据性质2,1 ~ i1-1一定不是正确的起始点。此时i1为起始点的候选。

2. 将sum清0,并从i1出发,假如又遇到i2使sum(gas[i] - cost[i]) < 0 时,说明i1出发无法绕一圈,更具性质1,排除i1。又因为i1+1 ~ i2-1都能从i1出发到达,。根据性质2,它们也必然不是起始点。此时i2为起始点的候选。

3. 以此类推,直到遇到ik,使从ik出发可以到达ik+1 ~ n-1。

其中步骤0可以合并到1~3的扫描中,一个pass来得到解。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start = 0, netGasSum = 0, curGasSum = 0;
        for(int i=0; i<cost.size(); i++) {
            netGasSum += gas[i] - cost[i];
            curGasSum += gas[i] - cost[i];
            if(curGasSum<0) {
                start = i+1;
                curGasSum = 0;
            }
        } 
        if(netGasSum < 0) return -1;
        return start;
    }
};

7 comments:

  1. 谢谢!看了你的解释,我终于明白了!

    ReplyDelete
  2. 你的解釋是我看到最清楚的

    ReplyDelete
  3. 支持,你的很多题解释的详细又直观,十分感谢

    ReplyDelete
  4. 我觉得楼主讲的很好,但是有个细节楼主没有cover到,根据楼主的解释:
    1. ...此时i1为起始点的候选。
    2. ...此时i2为起始点的候选。
    其实此时start应该分别是i1 + 1和i2 + 1
    对于Sum小于0,说明当前的start点到不了i,所以当前的start不是答案,并且因为start 可以到 i-1,说明答案不在这些点中,而且因为直到i-1,sum都是大于0的,所以说明gas[i] – cost[i] 一定小于0,所以i也不是start,所以start = i + 1 而不是start = i

    ReplyDelete
  5. 总结一下,就是
    0. 如果对所有加油站的sum(gas[i] - cost[i])<0,则无解。否则进入1。

    1. 从0开始计算sum(gas[i] - cost[i]),当遇到i1使sum<0时,说明从0出发无法到达i1。根据性质1,0不是起始点。而由于从0出发已经到达了1 ~ i1-1。根据性质2,1 ~ i1-1一定不是正确的起始点。而且因为直到i1-1,sum都是大于0的,所以说明gas[i1] – cost[i1] 一定小于0,所以i1也不是start,所以start = i1 + 1 而不是start = i1

    2. 将sum清0,并从i1出发,假如又遇到i2使sum(gas[i] - cost[i]) < 0 时,说明i1出发无法绕一圈,更具性质1,排除i1。又因为i1+1 ~ i2-1都能从i1出发到达,。根据性质2,它们也必然不是起始点。此时i2为起始点的候选。而且因为直到i2-1,sum都是大于0的,所以说明gas[i2] – cost[i2] 一定小于0,所以i2也不是start,所以start = i2 + 1 而不是start = i2

    3. 以此类推,直到遇到ik,使从ik出发可以到达ik+1 ~ n-1。

    ReplyDelete
  6. 性质2好像没有用啊。

    如果0~i1间有正确起始点。假设是x,那么sum(x~i1)是非负,那么sum(0~x-1)肯定是负。也就是说,在之前的迭代中就已经移动start到x或x之前的位置了。

    对于i1到i2的情况应该也是一样



    也就是说,即使不是唯一解,楼主的算法也可以找到其中一个结,楼主可不可以确认一下?

    ReplyDelete
  7. 从0开始计算sum(gas[i] - cost[i]),当遇到i1使sum<0时,说明从0出发无法到达i1。根据性质1,0不是起始点。而由于从0出发已经到达了1 ~ i1-1。根据性质2,1 ~ i1-1一定不是正确的起始点。而且因为直到i1-1,sum都是大于0的,所以说明gas[i1] – cost[i1] 一定小于0,所以i1也不是start,所以start = i1 + 1 而不是start = i1,这段理解起来很困难,我觉得应该有数学的证明才能够解释清楚。。。这样直接给结论有点难以接受。

    ReplyDelete