Java solution - Recursion with binary search


  • 0
    D

    Idea is to try all positions based on the rules and see if the last stone can be reached:

    public boolean canCross(int[] stones) {
    	return directedFind(0, 0, stones);
    }
    
    private boolean directedFind(int offset, int unit, int[] stones) {
    	if (offset == stones.length - 1) {
    		return true;
    	}
    	if(offset > stones.length){
    		return false;
    	}
    	int mid = Arrays.binarySearch(stones, stones[offset]+unit);
    	int lo = Arrays.binarySearch(stones, stones[offset]+unit+1);
    	int hi = Arrays.binarySearch(stones, stones[offset]+unit-1);
    		
    	boolean result = false;
    	if(mid >= 0 && mid != offset  && mid > offset){
    		result |=  directedFind(mid, stones[mid]-stones[offset], stones);
    	}
    	if(!result && lo >=0 && lo != offset && lo > offset){
    		result |=  directedFind(lo, stones[lo]-stones[offset], stones);
    	}
    	if(!result && hi >=0 && hi != offset  && hi > offset){
    		result |=  directedFind(hi, stones[hi]-stones[offset], stones);
    	}
    	return result;
    }
    

Log in to reply
 

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