LeetCode 题解:45. 跳跃游戏 II,贪心从后向前,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/jump-game-ii/
解题思路:
该题是55. 跳跃游戏的加强版。
由于该题保证最终能够到达
nums.length - 1
位置,我们只要考虑每次都跳跃到当前已知能够到达的最远位置即可。假设当前已经在某个位置
target
,只需从前遍历数组,查找最先能够跳跃到当前点的位置,也就是找到了这次跳跃的最大距离。之后将target
移动到这个位置,完成向前跳跃一次。不断重复回退的过程,当到达起始点时,就知道了最小跳跃次数。
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/22a6d639364627e2e8d816d51】。文章转载请联系作者。
评论