A different Java solution, simulating the car traveling


  • 0
    J

    My algorithm will actually simulate the car traveling a circle. No short-cut, nor smart thinking. However it is pretty fast with a little bit of optimization.

    public int canCompleteCircuit(int[] gas, int[] cost) {
         return travel(gas, cost, 0);
    }
    
    private int travel(int[] gas, int[] cost, int start) {
    	//Terms: "negative station i" if gas[i] - cost[i] < 0,
    	//      "postive station i"  if gas[i] - cost[i] >= 0
    	//skip the 'negative' station as the starting point.
    	while (start < gas.length && gas[start] - cost[start] < 0) start++;
    	if (start == gas.length)  //recursion exit if no start point found.
    		return -1;
    	int sumGas = 0, sumCost = 0;  //accumulated gas and cost.
    	boolean canComplete = true;
    	int lastStation = start; //To record the last station failed.
    	//travel the first part of the circle.
    	for (int i = start; i < gas.length; i++) {
    		sumGas += gas[i];
    		sumCost += cost[i];
    		if (sumCost > sumGas) {
    			canComplete = false;
    			lastStation = i;
    			break;
    		}
    	}
    	// travel the second part of the circle.
    	if (canComplete) {
    		for (int i = 0; i < start; i++) {
    			sumGas += gas[i];
    			sumCost += cost[i];
    			if (sumCost > sumGas) {
    				canComplete = false;
    				break;
    			}
    		}
    	}
    	if (canComplete)
    		return start;
    	else {
    		return travel(gas, cost, lastStation+1); //try the next starting point.
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.