写点什么

LeetCode 题解:55. 跳跃游戏,贪心,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 22 日
LeetCode题解:55. 跳跃游戏,贪心,JavaScript,详细注释

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


解题思路:


  1. 该题其实并不需要真正模拟跳跃,而是要知道从第一点开始跳,最远可以达到的索引是多少。

  2. 例如遍历[2,3,1,1,4]

* 从索引 0 最多可以跳到 2(0+2),那么 0~2 都在可到达的范围内。

* 从索引 1 最多可到达 4(1+3),即可以到达最后位置。

  1. 例如遍历[3,2,1,0,4]

* 从索引 0 最多可以跳到 3(0+3),那么 0~3 都在可达到的范围内。

* 从 1 最多可以跳到 3(1+2),从 2 最多可以跳到 3(2+1),从 3 无法继续跳跃。

* 因此从 0 开始跳,最多可到达的位置就是 3,永远不可能到达 4。

* 当遍历到 4 时,当前索引已经超过了最多可到达位置 3,也就是已经无法继续向前走,4 之后的所有位置都无法到达。


/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let max = 0 // 存储遍历到的所有位置向前走之后,可到达的最远位置
for (let i = 0; i < nums.length; i++) {
// 如果当前位置已经超过了最远位置,表示从之前的所有位置向前走,都不可能到达i及其之后的位置
if (i > max) {
return false
}
// 计算至今遍历到的所有位置,向前走nums[i]步后,可能到达的最大位置
max = Math.max(max, i + nums[i])
// 如果最远位置已可到达最后一个位置,即可退出循环
if (max >= nums.length - 1) {
return true
}
}
};
复制代码


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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:55. 跳跃游戏,贪心,JavaScript,详细注释