55. Jump Game

三刷 06/2022

Version #1 Greedy

跟二刷写的稍微有点不一样

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 91.43% of Java online submissions for Jump Game.

Memory Usage: 67.9 MB, less than 53.75% of Java online submissions for Jump Game.

class Solution {

    public boolean canJump(int[] nums) {

        // If at index we can jump n steps, then all indices between [index + 1, index + n] can be reached

        // We can iterate over the nums and keep track of the furthest index that we can reach

        // If current index > furthest index, then return false

        int furthest = 0;

        for (int i = 0; i < nums.length; i++) {

            if (furthest < i) {

                return false;

            }

            furthest = Math.max(furthest, i + nums[i]);

        }

        return true;

    }

}

二刷 06/2022

Version #1 Greedy

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 88.45% of Java online submissions for Jump Game.

Memory Usage: 68.8 MB, less than 14.63% of Java online submissions for Jump Game.

class Solution {

    public boolean canJump(int[] nums) {

        int p = 0;

        int i = 0;

        for (i = 0; i <= p && i < nums.length; i++) {

            p = Math.max(p, i + nums[i]);

        }

        return i == nums.length;

    }

}

一刷

Version #1 Greedy
Iterate through the array, doing 2 things
1. Check if current index can be reached
2.Update the furthest index we can reach so far
As long as the furthest index is larger than the last index, we know we can reach

Time O(n)
97.15 %
class Solution {
    public boolean canJump(int[] nums) {
if (nums == null || nums.length <= 1) {
return true;
}
int furthest = nums[0];
for (int i = 0; i < nums.length; i++) {
if (i > furthest) {
return false;
}
furthest = Math.max(furthest, i + nums[i]);
if (furthest >= nums.length - 1) {
return true;
}
}
return false;
}
}