Java Solution Using DP + HashMap


  • 0
    C
    public boolean canCross(int[] stones) {
        if (stones == null || stones.length == 0) {
            return true;
        }
        
        HashMap<Integer, boolean[]> map = new HashMap<Integer, boolean[]>();
        int last = stones[stones.length - 1];
        if (last == Integer.MAX_VALUE) {
            return false;
        }
        int maxStep = maxStep(last);
        boolean[] cur = new boolean[maxStep + 1];
        cur[0] = true;
        map.put(0, cur);
        
        for (int i = 1; i < stones.length; i++) {
            int unit = stones[i];
            cur = new boolean[maxStep + 1];  //whether I can jump j step to this unit 
            for (int j = 1; j < cur.length; j++) {
                if (!map.containsKey(unit - j)) {
                    cur[j] = false;
                } else {
                    boolean[] pre = map.get(unit - j);
                    cur[j] = pre[j - 1] || pre[j];
                    if (j < cur.length - 1) {
                        cur[j] = cur[j] || pre[j + 1];
                    }
                }
            }
            map.put(unit, cur);
        }
        
        cur = map.get(last);
        boolean res = cur[0];
        for (int i = 1; i < cur.length; i++) {
            res = res || cur[i];
        }
        return res;
    }
    
    private int maxStep(int last) {
        int i = 1;
        int sum = 0;
        
        while (sum < last) {
            sum += i;
            i++;
        }
        return i - 1;
    }

Log in to reply
 

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