# 45 题跳跃游戏 2

# 题目链接

# 难度:中等

# 思路分析:

贪心

#

#

#

#

#

#

#

#

#

#

#

#

#

#

# 代码:

贪心

var jump = function(nums) {
  let step = 0;
  let jumpMax = 0; // 预计最远距离
  let last_canJumpMax = 0; // 上次可跳的最远距离
  for (let i = 0; i < nums.length - 1; i++) {
    const nowMax = nums[i] + i; // 当前最远距离
    jumpMax = Math.max(jumpMax, nowMax); // 下一步最远距离
    // 上次跳跃后 下一步的最远距离 需要再跳
    if (last_canJumpMax === i) {
      last_canJumpMax = jumpMax; // 最远距离更新
      step++; // 步数更新
    }
    // 最远距离超过终点
    if (last_canJumpMax >= len - 1) {
      break;
    }
  }
  return step;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归

function jump(nums) {
  let num = nums[0]; // 初始能跳的步数
  if (nums.length === 1) return 0;
  let total = 0; // 总共跳几次
  let everOne = [num]; // 每次经过的地方
  function jumpOne(newNums, oneNum) {
    let maxNum = 0; // 最远能跳多远
    let maxIndex = oneNum; // 预设最大值
    if (oneNum + 1 >= newNums.length) {
      // 步数已经足够到达最后一个位置
      maxIndex = newNums.length - 1;
    } else {
      // 每个点都跳一遍
      for (let i = 1; i <= oneNum; i++) {
        // 当前已跳步数大于 之前缓存的最大步数 更新最远距离
        if (i + newNums[i] >= maxNum) {
          maxNum = newNums[i] + i; // 最远能跳多远
          maxIndex = i; // 最远跳的目标位置
        }
      }
    }
    total++; // 当前跳跃次数
    everOne.push(newNums[maxIndex]); // 每次到达的位置
    if (maxIndex !== newNums.length - 1) {
      newNums.splice(0, maxIndex); // 清除已跳的元素
      jumpOne(newNums, newNums[0]);
    }
  }
  jumpOne(nums, num);
  return total;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 鼓励我一下:

觉得还不错的话,给我的项目点个star

# 点个Star支持我一下~

最后更新时间: 7/2/2020, 4:27:35 PM