Java solution beating 100%


  • 0
    M

    Some hints:

    1: used a recursive function when multiple step lengths are possible

    2: Used a cache, since the recursive function is called many times with the same parameters

    3: if only one step length is possible (1), use iterative version (to minimize stack overflows)

    4: start checking larger leaps (which are more likely to get a fast solution)

    5: if the "jump" recursive function returns 1, do not invoke it with other values, since you won't get a better mark.

    public class Solution {
        int[] jumpsCache;
        private int jump(int[] nums,int from) {
            if(from >= nums.length - 1) return 0;
            if(from + nums[from] >= nums.length - 1 ) return 1;
            if(jumpsCache[from] != 0) return jumpsCache[from];
            final int startFrom = from;
            int directJumps = 0;
            while(nums[from]==1) {
                directJumps++;
                from++;
                if(from == nums.length - 1) {
                    return directJumps;
                } else if(nums[from] == 0) {
                    return -1;
                }
            }
            int jumps = -1;
            for(int i = nums[from] ; i >= 1 ; i--) {
                int nj = jump(nums,from+i);
                if(nj >= 0 && (jumps == -1 || nj + 1 < jumps)) {
                    jumps = nj + 1;
                    if(nj == 1) break;
                }
            }
            jumpsCache[startFrom] = jumps + directJumps;
            return jumps + directJumps;
        }
        public int jump(int[] nums) {
            jumpsCache = new int[nums.length];
            return jump(nums,0);
        }
    }

Log in to reply
 

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