Leetcode#45 Jump Game II
type
status
date
slug
summary
tags
category
icon
password
给定一个数组，从下标为0开始，往右跳，下标对应的值表示其能跳的最远距离。求最少X步，能跳到最后一个元素？
简单思路
最近看SICP看的比较多，第一个想到的办法，就是递归。
- 对于数组$[a,a_1...a_n]$，找到能跳到最后的最小下标$m$
- 对于数组$[a,a_1...a_m]$，找到能跳到最后的最小下标$l$
- ……
- 当最后数组长度为1的时候，说明已经到头了
改进
在上面的算法中，从左到右，
- 很多位置($i$)能达到的最远距离($nums[i]+i$)，都被计算了多次。
- 就算是每个位置的最远距离缓存/保存起来，迭代次数并不会减少。
改进的思路，依然是从左往右遍历
整理一下
Loading...