55. 跳跃游戏

[heyLiup]

https://leetcode.cn/problems/jump-game/

解法一

var canJump = function(nums) {
    let curIndex = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] + i >= curIndex) {
            curIndex = i
        }
    }
    return curIndex === 0
};

解法二

var canJump = function (nums) {
    if (nums.length < 2) {
        return true;
    }
  let dfs = (n) => {
    for (let i = 0; i < n; i++) {
      if (nums[i] > n - i) {
         return true;
      }
      if (nums[i] === n - i && n === nums.length - 1) {
          return true;
      }
    }
    return false;
  };
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
        if (nums[i] === (nums[i + 1])) continue;
      if (!dfs(i)) {
        return false;
      }
    }
  }
  return true;
};

解法三

var canJump = function (nums) {
  let length = nums.length;
  if (length <= 1) {
      return true;
  }
  const getMaxDistance = (step) => {
    let temp = 0;
    for (let i = 0; i <= step; i++) {
      let target = i + nums[i];
      if (temp < target) {
        temp = target;
      }
    }
    return temp;
  };

  let map = [0, nums[0]];  // 计算出每一步最大能到哪里

  for (let i = 2; i < length; i++) {
    if (map[map.length - 1] >= length -1) {
        return true;
    }
    map[i] = getMaxDistance(map[i - 1]);
  }
  console.log(map);
  return map[map.length - 1] >= length -1;
};

解法四
动态规划 dp为第i步能到达的最远距离

var canJump = function (nums) {
    const dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    if (nums.length <= 1) return true;
    for (let i = 1 ; i < nums.length; i++) {
        if (dp[i - 1] < i) {
            return false;
        }
        dp[i] = Math.max(dp[i - 1], nums[i] + i)
    }
    console.log(dp);
    return dp[dp.length - 2] >= nums.length - 1;
};

跳跃游戏二
https://leetcode.cn/problems/jump-game-ii/

基于解法三改造

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let length = nums.length;
  if (length <= 1) {
      return 0;
  }
  const getMaxDistance = (step) => {
    let temp = 0;
    for (let i = 0; i <= step; i++) {
      let target = i + nums[i];
      if (temp < target) {
        temp = target;
      }
    }
    return temp;
  };

  let map = [0, nums[0]];

  for (let i = 2; i < length; i++) {
    if (map[map.length - 1] >= length -1) {
        return map.length - 1;
    }
    map[i] = getMaxDistance(map[i - 1]);
  }
  console.log(map);
  return map.length - 1;
};