45. Jump Game II

Posted on | Edited on | Views:

LeetCode

Greedy, Two Pointers, Slicing Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int jump(int[] nums) {
        int len=nums.length;
        if(len<2) return 0;
        int maxPos=nums[0],maxSteps=nums[0];
        int jumps=1;
        for(int i=1;i<len;i++){
            if(maxSteps<i){
                jumps++;
                maxSteps=maxPos;
            }
            maxPos=Math.max(maxPos,i+nums[i]);
        }
        return jumps;
    }
}

Brute Force, Time Complexity: O(2^N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
class Solution {
    public int jump(int[] nums) {
        int len=nums.length;
        Integer[] minStep=new Integer[len];
        minStep[0]=0;
        for(int i=1;i<len;i++){
            for(int j=i;j<i+nums[i-1];j++){
                if(minStep[j]==null) minStep[j]=minStep[i-1]+1;
                minStep[j]=Math.min(minStep[i-1]+1,minStep[j]);
                if(j==len-1) return minStep[len-1];
            }
        }
        return minStep[len-1];
    }
}*/

0%