LeetCode 题解:55. 跳跃游戏,贪心,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/jump-game/
解题思路:
该题其实并不需要真正模拟跳跃,而是要知道从第一点开始跳,最远可以达到的索引是多少。
例如遍历
[2,3,1,1,4]
:
* 从索引 0 最多可以跳到 2(0+2),那么 0~2 都在可到达的范围内。
* 从索引 1 最多可到达 4(1+3),即可以到达最后位置。
例如遍历
[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 之后的所有位置都无法到达。
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/d7a75c1334e112aa4496866ea】。文章转载请联系作者。
评论