《leetcode-php》一个环路加油站，是否能走一圈

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.

在一个环形路上有N个加油站，第i个加油站定义为gas[i]。你的汽车的油箱是无限容量的，她从第i个加油站到第i+1个加油站要用cost[i]的油。你在其中一个加油站开始跑，且油箱是空的。返回可以跑完一圈的起始加油站，如果都不能跑完一圈，则返回-1。注意：这个解是唯一的。

解法：从头开始遍历，算出从该点一直走下去，如果油箱出现负数，则该点不能作为起始点。且路途经过的点也不能成为起始点，这个是为什么呢？是因为，除了最后一个点，前面经过的点，一定油箱的油都是正的，也就是说，你从中间的点作为起始，肯定到最后一个点还是负的，所以如果油箱出现负数，则该点不能作为起始点，且路途经过的点也不能成为起始点。然后以下一个点作为起始点，继续计算，如果一直都是正数，则把之前统计出来的负数的和与这个正数相加，判断是否为负，如果是负数，则不可能跑完一圈，如果是正数，则肯定能跑完。时间负责度是O(N)。

<?php
function canCompleteCircuit($arrGas, $arrCost) {
$start
= 0;
$count
= count($arrGas);
$restGas
= 0;
$leftRestGas = 0;
for ($i = 0;$i < $count;$i ++) {
$restGas += $arrGas[$i] - $arrCost[$i];
if ($restGas < 0) {
$start
= $i + 1;
$leftRestGas += $restGas;
$restGas
= 0;
}
}
return ($restGas + $leftRestGas) < 0 ? -1 : $start + 1;
}
$arrGas
= [1,2,3,4,5];
$arrCost = [3,4,5,1,2];
$ret
= canCompleteCircuit($arrGas, $arrCost);
print $ret;

最后

以上就是故意大神为你收集整理的《leetcode-php》一个环路加油站，是否能走一圈的全部内容，希望文章能够帮你解决《leetcode-php》一个环路加油站，是否能走一圈所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。