2014年5月6日星期二

Loop Solution - Gas Station - Math

It is a typical loop and math question: be sure to use remaining since the start is not necessary to be 0, and like gas.length+i+1, like i = nextStart…. since this one is not enough gas, there is no way new start is between last start and j… be confident on that during thinking...

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas == null || cost == null){
            return -1;
        }
        int i  = 0;
        int nextStart = i;
        while(i < gas.length){
            int j = i;
            int accumulatedGasAmount = 0;
            while(j < gas.length + i + 1){
                if(accumulatedGasAmount + gas[j % gas.length] < cost[j % gas.length]){
                    nextStart = j + 1;
                    break;
                }else {
                    if(j == gas.length + i){
                        return i;
                    }else{
                        accumulatedGasAmount = accumulatedGasAmount + gas[j % gas.length] - cost[j % gas.length];
                        j++;
                    }
                }
            }
            i =  nextStart;
        }
        return -1;
    }
}

没有评论: