055.Jump Game

Posted on | In

Solution 1: TLE

Normal DP.
Time: O(nk) (k is the largest input[i])
Space: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
    int len = nums.length;
    if (len < 2) return true;
    boolean[] dp = new boolean[len];
    dp[len - 1] = true;
    for (int i = len - 2; i >= 0; i--) {
        for (int j = 0; j <= nums[i]; j++) {
            if (dp[Math.min(i + j, len - 1)]) {
                dp[i] = true;
            }
        }    
    }
    return dp[0];
}

Solution 2: accepted 10ms

DP.
Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
public boolean canJump(int[] nums) {
    int len = nums.length;
    // if (len < 2) return true;
    int nextJump = 0;
    for (int i = 0; i < len - 1; i++) {
        nextJump = Math.max(nextJump - 1, nums[i]);
        if (nextJump == 0)
            return false;
    }
    return true;
}

Solution 3: accepted 8ms

7ms

1
2
3
4
5
6
7
8
9
public boolean canJump(int[] nums) {
    int last = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= last) {
            last = i;
        } 
    }
    return last == 0;
}

8ms

1
2
3
4
5
6
7
8
9
10
public boolean canJump(int[] nums) {
    int len = nums.length;
    int last = len - 1;
    for (int i = len - 2; i >= 0; i--) {
        if (i + nums[i] >= last) {
            last = i;
        } 
    }
    return last == 0;
}