45.跳跃游戏II

链接：45.跳跃游戏II
难度：Medium
标签：贪心、数组、动态规划
简介：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

题解 1 - javascript

• 编辑时间：2020-05-04
• 执行用时：84ms
• 内存消耗：36.43MB
• 编程语言：javascript
• 解法介绍：通过递归对每层判断后压栈。

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  const len = nums.length;
  if (len === 1) return 0;
  // console.log(len);
  let maxStep = 1;
  let maxIndex = nums[0];
  let tempMaxIndex = 0;
  const newArr = new Array();
  newArr[0] = 0;
  newArr[maxIndex] = 1;
  for (let i = 1; i < len; i++) {
    const num = nums[i];
    // console.log("==");
    // console.log("i:" + i);
    // console.log("num:" + num);
    // console.log("num+i:" + (num + i));
    if (i > maxIndex) {
      maxIndex = tempMaxIndex;
      newArr[maxIndex] = ++maxStep;
      if (newArr.length >= len) break;
    }
    const nextIndex = num + i;
    if (nextIndex >= tempMaxIndex) {
      tempMaxIndex = nextIndex;
    }
  }
  // console.log(newArr);
  let resIndex = len - 1;
  let res = newArr[resIndex];
  while (res === undefined) {
    res = newArr[++resIndex];
  }
  return res;
};

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：84ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：每次跳跃，获取当前可跳跃范围。

function jump(nums: number[]): number {
  const n = nums.length;
  if (n <= 1) return 0;
  let curP = 0;
  let maxP = nums[0];
  let ans = 1;
  while (maxP + 1 < n) {
    let nextMaxP = nums[curP];
    for (let i = curP + 1; i <= maxP; i++) {
      nextMaxP = Math.max(nums[i] + i, nextMaxP);
    }
    curP = maxP;
    maxP = nextMaxP;
    ans++;
  }
  return ans;
}