LeetCode 55. Jump Game

1. 解法1: 遍历

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] result = new boolean[nums.length];
        
        if(nums.length < 2) {
            return true;
        }
        
        result[0] = true;
        for (int i = 0; i < nums.length - 1; i++) {
            if ( result[i] ) {
                int step = nums[i];
                while(step > 0) {
                    int des = i + step;
                    if ( des == nums.length -1 ) {
                        return true;
                    }
                    if ( des < nums.length - 1 ) {
                        result[i+step] = true;
                    }
                    step--;
                }
            }
        }
        return false;
    }
}

2. 解法2: Greedy

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length < 2) {
            return true;
        }
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if ( maxReach == i && nums[i] == 0 ) {
                return false;
            }
            maxReach = Math.max(maxReach, nums[i] + i);
            if ( maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}