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個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;
    	}
    }