LeetCode — Gas Station

LeetCode — Gas Station

标题陈述:

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个站的消耗为cost[i],能或不能够找到三个视角,能够跑完瓦斯[0…n)一圈。

解法一:

独家以每种加油站作为出发点(stopNo)实行测验 , StopNo ∈瓦斯[i,n):
delta= gasInCar(起头化为0) + 瓦斯[i] – cost[i]
比如delta >=
0,累加瓦斯InCar,去下一站i,累加成功达到下一站的次数:counter。固然counter到达瓦斯.Length,重回i。
否则,重置gasInCar = 0,stopNo++。i=下一站,counter重置为0。

鉴于解法为O(N^2)的时刻复杂度,不能够透过测验数据:

代码:

public int CanCompleteCircuit(int[] gas, int[] cost) {

        var gasInCar = 0;
        var stopNo = 0;

        var i = 0;
        var counter = 0;
        while(stopNo < gas.Length){

            if(gas[i] + gasInCar < cost[i]){
                // failed , start at a new place and re count again
                gasInCar = 0;
                stopNo ++;
                i = NextStop(stopNo, gas.Length);
                counter = 0;
            }
            else{
                gasInCar += gas[i]-cost[i];
                i = NextStop(i, gas.Length);
          counter ++;
            }

            if(counter == gas.Length){
                return i;
            }
        }

        return -1;
    }

    private int NextStop(int stop,int len){
        if(stop < len - 1){
            stop ++;
        }
        else {
            stop = 0;
        }
        return stop;
    }

解法二:
将此题分解为三个小标题:
1.是否可实现一圈
2.找到落脚点

存车中剩余瓦斯为瓦斯InCar=0,delta为近年来站到下一站的瓦斯[i]-cost[i],startAt为注重点。
贰回遍历瓦斯[i…n-1] :
假如delta >= 0 : 瓦斯InCar += delta(积存车中gas)
倘使小于0(即不可达):瓦斯InCar 设为 delta,startAt =
i,即复位当前点为着重点以及车中的瓦斯
历次积攒totalDelta

聊到底推断totalDelta 是还是不是高于0=能或无法成功一圈。

福衢寿车代码:

public int CanCompleteCircuit(int[] gas, int[] cost) 
    {
        var gasInCar = 0; 
     var totalDelta = 0; 
     var startAt = 0; 

     for (var i = 0; i < gas.Length; i++) {
      var delta = gas[i] - cost[i];

      if (gasInCar >= 0) { 
       gasInCar += delta;
      } else {
       gasInCar = delta;
       startAt = i;
      }
      totalDelta += delta;
     }

     if (totalDelta >= 0){
      return startAt;
     }else{
      return -1;
     }
    }

 

— Gas Station 标题陈述: There are N
瓦斯 stations along a circular route, where the amount of 瓦斯 at station
i is 瓦斯[i]. You have a car with an unlimited gas tank a…

相关文章