写点什么

LeetCode 题解:45. 跳跃游戏 II,贪心从后向前,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 09 日
LeetCode题解:45. 跳跃游戏 II,贪心从后向前,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/jump-game-ii/



解题思路:



  1. 该题是55. 跳跃游戏的加强版。

  2. 由于该题保证最终能够到达nums.length - 1位置,我们只要考虑每次都跳跃到当前已知能够到达的最远位置即可。

  3. 假设当前已经在某个位置target,只需从前遍历数组,查找最先能够跳跃到当前点的位置,也就是找到了这次跳跃的最大距离。之后将target移动到这个位置,完成向前跳跃一次。

  4. 不断重复回退的过程,当到达起始点时,就知道了最小跳跃次数。



/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
let target = nums.length - 1; // 初始时在最后位置,向前查找
let step = 0; // 统计跳跃次数
// 当target===0,即已经回退到起始点时,退出循环
// 如果进入循环,会导致多向后退一步
while (target > 0) {
// 每次循环都从前开始遍历
for (let i = 0; i < target; i++) {
// 找到第一个能够到达当前所处位置的点
// 也就是从i跳跃了最大距离,到达了target
if (i + nums[i] >= target) {
// 将target移动到i位置,即为回退一次
target = i;
// 每回退一次,跳跃次数加1
step++;
// 继续遍历已无意义,提前退出,否则会超时
break;
}
}
}
return step;
};



发布于: 2020 年 12 月 09 日阅读数: 14
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:45. 跳跃游戏 II,贪心从后向前,JavaScript,详细注释