题目地址(opens new window)

  • 🙂 第一次练习 2020å¹´4月4日 这个题目看过老师的讲解,还是比较可以。用贪心,确实比较巧妙
  • 😄 第二次练习 2020å¹´4月17日 第二次练习,还是能记得贪心的大概思路,不过 需要注意边界条件判断问题

# 贪心算法

解题代码

public boolean canJump(int[] nums) {
    if (nums == null)
        return false;

    int endReachable = nums.length - 1;
    for(int i = nums.length - 1; i >= 0; i --)
        if (nums[i] + i >= endReachable)
            endReachable = i;
    return endReachable == 0;
}

老师讲的另一种解法,自己实现

  • 用一个状态位记录当前位置是否可达,而后循环当前位置的值持续向后标记
public boolean canJump(int[] nums) {
    if (nums == null)
        return false;

    boolean[] markList = new boolean[nums.length];
    markList[0] = true;
    for (int i = 0; i < nums.length; i++) {
        if (!markList[i])
            continue;
        for (int j = i; j <= i + nums[i]; j++) {
            if (j == nums.length)
                break;
            markList[j] = true;
        }
    }
    return markList[nums.length - 1];
}

# 易错点

  • 边界条件判断
最后编辑时间: 7/14/2020, 9:21:47 AM