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


2019-8-29 星期四 开始吧

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

6478a065a75421baafc994368e4fe464.png


题目描述

一个环形路上有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;
        
    }

Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode基础刷题之PHP解析(131. Palindrome Partitioning)

>> 下一篇: Golang 中互斥锁与读写锁的简单使用