Leetcode基础刷题之PHP解析(134. Gas Station）

2019-8-29 星期四 开始吧

上一题链接Leetcode基础刷题之PHP解析(131. Palindrome Partitioning）

题目描述

一个环形路上有n个加油站，gas[i]表示每个加油站上你能加的油，cost[i]表示你从i站到i+1站所需要的油，让我们求是否存在从一个起点出发，能返回到原点加油站的开始起点站，注意想要走完一圈加油站，那么前提条件是gas整体肯定要大于cost。

题目分析

每到一个站，需要重新计算和，剩余的gas+当前的gas值-消费的cost，判断是否大于0，0可以继续，如果是小于0，就说明这个点之前的所有的加油点都不能作为他的起始点，所以我们新的起始点就应该是$i+1,最后判断一下变量是否小于0是的话说明不存在直接返回-1，否则返回起始点。

代码实现

    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    function canCompleteCircuit($gas, $cost) {
        $sum=$total=0;$start=0;
        
        for($i=0;$i<count($gas);$i++){
            $sum +=$gas[$i]-$cost[$i];
            $total +=$gas[$i]-$cost[$i];

            if($sum <0) {
                $start=$i+1;
                $sum=0;
            }
        }
        
      return  $total<0?-1:$start;
        
    }