134. Gas Station

2016-11-23  本文已影响11人  exialym

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.
遍历的方法,是对的,但是超时了:

var canCompleteCircuit = function(gas, cost) {
    var start = 0;
    var num = gas.length;
    while (start<gas.length) {
        var remain = 0;
        for (let i = start; i < num; i++) {
            remain += gas[i] - cost[i];
            if (remain<=0)
                break;
        }
        if (remain>=0&&start===0) {
            return start;
        }
        if (remain<=0) {
            start++;
            continue;
        }
        for (var i = 0; i < start; i++) {
            remain += gas[i] - cost[i];
            if (remain<=0)
                break;
        }
        if (remain>=0&&i === start - 1)
            return start;
        start++;
    }
    return -1;
};

仔细想想,有两点:
如果油的总量大于需要花费的总量,一定存在解。
如果一辆车从A开始,到达不了B,那么从A和B之间任何一站开始都到达不了B。
所以我们从头开始遍历数组,并记录油箱中的剩余,如果小于0了,那就意味着此次出发的点到不了当前点,得从当前点的下一点出发。遍历到最后,判定一下是否有唯一解,返回最后设定的起点。

var canCompleteCircuit = function(gas, cost) {
    var start = 0;
    var total = 0;
    var tank = 0;
    //if car fails at 'start', record the next station
    for(var i = 0;i < gas.length;i++) {
        tank = tank + gas[i] - cost[i];
        if(tank < 0) {
            start = i + 1;
            total += tank;
            tank = 0;
        }
    }
    return (total + tank < 0) ? -1 : start;
};
上一篇下一篇

猜你喜欢

热点阅读