当前位置：首页 > news >正文

LeetCode -- Gas Station

news 来源：原创 2024/5/9 22:41:13

题目描述：

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个gas站，到达第i个站的消耗为cost[i]，能否找到一个出发点，可以跑完gas[0...n)一圈。

解法一：

分别以每个加油站作为出发点(stopNo)进行测试 , StopNo ∈gas[i,n)：
delta= gasInCar（初始化为0） + gas[i] - cost[i]
如果delta >= 0，累加gasInCar，去下一站i，累加成功到达下一站的次数：counter。如果counter达到gas.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.找到出发点

存车中剩余gas为gasInCar=0，delta为当前站到下一站的gas[i]-cost[i]，startAt为出发点。
一次遍历gas[i...n-1] :
如果delta >= 0 : gasInCar += delta(积累车中gas)
如果小于0（即不可达）：gasInCar 设为 delta，startAt = i，即重置当前点为出发点以及车中的gas
每次积累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;
    	}
    }