算法题(76):跳跃游戏II
审题:
在确定一定可以到达数组末尾位置的前提下,查找跳跃次数最少得跳跃次数思路:
方法一:反向查找最少次数
首先我们反向来思考,若我们要跳到pos位置(初始化为n-1位置),最后一步有多情况,但是最后一步跳出位置的索引值越小,跳跃次数越少。以此类推,我们将该跳出位置更新为pos,重复进行操作,直到pos==0结束查找(因为题目确保一定可以到达末尾,且第一步一定是从0索引出发)方法二:正向查找最少次数
由于反向查找需要的时间复杂度是O(n^2),所以我们优化一下时间复杂度。
我们维护一个maxdistance,他负责维护选择完最优落点后的可达最远距离,在maxdiatance可以覆盖到的索引处寻找下一个最优跳跃点,最优跳跃点就是落在该位置后可以走的距离比其他位置远。维护一个end他表示当前索引可以到达的最远索引,也就是搜索最优落点的范围,当i==end时,count++,因为此时已经选择完下一个落点,跳越数++
解题:
方法一:反向查找
方法二:正向查找
45. 跳跃游戏 II - 力扣(LeetCode)