美文网首页
134. Gas Station

134. Gas Station

作者: exialym | 来源:发表于2016-11-23 16:07 被阅读11次

    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;
    };
    

    相关文章

      网友评论

          本文标题:134. Gas Station

          本文链接:https://www.haomeiwen.com/subject/lkhvpttx.html