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