Pengjielee's blog

题目

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 3 * 10^4
0 <= nums[i] <= 10^5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

参考代码1：

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
  //数组的长度
  const n = nums.length;
  //可以向右跳跃的最大位置
  let rightMost = 0;

  for (let i = 0; i < n; ++i) {
    if (i <= rightMost) {
      //更新向右跳跃的最大位置
      rightMost = Math.max(rightMost, i + nums[i]);
      if (rightMost >= n - 1) {
        return true;
      }
    }
  }
  return false;
};

参考代码2：

var canJump = function (nums) {
  //数组的长度
  const n = nums.length;
  //可以向右到达的最远位置
  let reach = 0;

  for (let i = 0; i < n; i++) {
    if(i > reach) {
      return false;
    }
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
};

参考代码3：优化

var canJump = function (nums) {
  //数组的长度
  const n = nums.length;
  //可以向右到达的最远位置
  let reach = 0;

  for (let i = 0; i <= reach && reach < n - 1; i++) {
    reach = Math.max(reach, i + nums[i]);
  }
  return reach >= n - 1;
};

参考代码4：倒序遍历，寻找最早开始出发的位置

var canJump = function (nums) {
  //数组的长度
  const n = nums.length;
  let last = n - 1;

  for (let i = n - 2; i >= 0; i--) {
    if(i + nums[i] >= last){
      last = i;
    }
  }
  return last === 0;
};

参考代码5：动态规划

从后往前分析，首先判断倒数第二个元素能否到达最后一个元素，如果可以，我们将不再考虑最后一个元素，因为根据刚才的分析如果可以到达倒数第二个，那么也可以到达最后一个元素。

然后依次往前递推，如果都能跳到的话，我们最后应该分析的就是第一个元素能否跳到第二个元素上。

作者：yangtianrui95 链接：https://leetcode-cn.com/problems/jump-game/solution/dong-tai-gui-hua-yu-tan-xin-suan-fa-jie-jue-ci-wen/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

var canJump = function (nums) {
  if (nums === null) {
    return false;
  }

  //数组的长度
  const len = nums.length;

  const dp = new Array(len).fill(false);
  dp[0] = true;

  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      // 如果之前的j节点可达，并且从此节点可以到跳到i
      if (dp[j] && nums[j] + j >= i) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[len - 1];
};