Share my idea prograss from brute force to greedy stragedy


  • 2
    C
    //brute force : time limit exceeded
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int ret = -1;
        for (int i = 0; i < gas.length; i++) {
        	int sum = 0, count = 1;
        	for (int start = i; count <= gas.length; start++){
        		sum += gas[start % gas.length] - cost[start % gas.length];
        		count++;
        		if(sum < 0) break;
        	}
        	if(sum >= 0) return i;
    	}
        return ret;
    }
    // pruning algorithm : 1ms
    // if sum of gas station from i to j is negative, then there are no start point from i to j.
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int ret = -1;
        for (int i = 0; i < gas.length; ) {
        	int sum = 0, count = 1, start = i;
        	for ( ; count <= gas.length; start++){
        		sum += gas[start % gas.length] - cost[start % gas.length];
        		count++;
        		if(sum < 0) break;
        	}
        	if(sum >= 0) return i;
        	else i = start + 1;
    	}
        return ret;
    }
    // greed strategy : 0ms
    // if sum of all of gas[i] - cost[i] is non-negative, there are gas station where can be start
    // if sum of gas station from i to j is negative, then there are no start point from i to j
    // we choose the gas station that first point of sum of subrange is non-negative and other subrange is negative.
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0, localSum = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
        	localSum += gas[i] - cost[i];
        	if(localSum < 0){
        		sum += localSum;
        		localSum = 0;
        		start = i + 1;
        	}
    	}
        return sum + localSum < 0 ? -1 : start;
    }

  • 0
    C

    please forget my poorly english


Log in to reply
 

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