题解 | #跳跃游戏(一)#

思路: 假设当前在 i 位置上，能否跳到 i 位置上，要看 [0, i - 1] 范围上，是否存在 j 位置，j 满足

1. j + nums[j] >= i (j 能跳跃到当前位置上)
2. dp[j] == true (J 位置是能通过前面的跳跃到达)

用力通过率: 60%

public boolean canJump (int[] nums) {
        // write code here
        if (1 == nums.length) {
            return true;
        }
        // 动态规划
        // 状态表示: dp[i] 表示的是能否跳跃到 i 位置上
        boolean[] dp = new boolean[nums.length];
        // 初始化
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }

思路: 如果当前位置 i 可达，那么 [i, i + nums[i]] 这个范围内的位置都可达

用例通过率: 70%

public static boolean canJump(int[] nums) {
        // write code here
        if (1 == nums.length) {
            return true;
        }
        // 动态规划
        // 状态表示: dp[i] 表示的是能否跳跃到 i 位置上
        boolean[] dp = new boolean[nums.length];
        // 初始化
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 0; i < dp.length; i++) {
            if (!dp[i]) {
                continue;
            }
            int num = nums[i];
            int account = 1;
            if (i + num >= nums.length - 1) {
                return true;
            }
            while (account <= num) {
                dp[i + account] = true;
                account++;
            }
        }
        return dp[dp.length - 1];
    }

思路: 定义一个 jump 数组 jump[i]: i 所能到达的最远位置

用例通过率: 100%

public static boolean canJump(int[] nums) {
        if (1 == nums.length) {
            return true;
        }
        int[] jump = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            jump[i] = i + nums[i];
        }
        int index = 0;
        int max = jump[0];
        while (index < nums.length && index <= max) {
            max = Math.max(max, jump[index]);
            index++;
        }
        if (index == nums.length) {
            return true;
        }
        return false;
    }

完整代码如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    
    /**********************************************************************************/
    // 思路: 假设当前在 i 位置上，能否跳到 i 位置上，要看 [0, i - 1] 范围上，是否存在 j 位置，j 满足
    // 1）j + nums[j] >= i (j 能跳跃到当前位置上)
    // 2）dp[j] == true (J 位置是能通过前面的跳跃到达)
    // 用力通过率: 60%
    /*
    public boolean canJump (int[] nums) {
        // write code here
        if (1 == nums.length) {
            return true;
        }
        // 动态规划
        // 状态表示: dp[i] 表示的是能否跳跃到 i 位置上
        boolean[] dp = new boolean[nums.length];
        // 初始化
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }
    */
    
    /**********************************************************************************/
    // 思路: 如果当前位置 i 可达，那么 [i, i + nums[i]] 这个范围内的位置都可达
    // 用例通过率: 70%
    /*
    public static boolean canJump(int[] nums) {
        // write code here
        if (1 == nums.length) {
            return true;
        }
        // 动态规划
        // 状态表示: dp[i] 表示的是能否跳跃到 i 位置上
        boolean[] dp = new boolean[nums.length];
        // 初始化
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 0; i < dp.length; i++) {
            if (!dp[i]) {
                continue;
            }
            int num = nums[i];
            int account = 1;
            if (i + num >= nums.length - 1) {
                return true;
            }
            while (account <= num) {
                dp[i + account] = true;
                account++;
            }
        }
        return dp[dp.length - 1];
    }
    */
    
    /**********************************************************************************/
    // 思路: 定义一个 jump 数组    jump[i]: i 所能到达的最远位置
    // 用例通过率: 100%
    public static boolean canJump(int[] nums) {
        if (1 == nums.length) {
            return true;
        }
        int[] jump = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            jump[i] = i + nums[i];
        }
        int index = 0;
        int max = jump[0];
        while (index < nums.length && index <= max) {
            max = Math.max(max, jump[index]);
            index++;
        }
        if (index == nums.length) {
            return true;
        }
        return false;
    }
}