跳跃游戏II
题目链接: https://leetcode.cn/problems/jump-game-ii
解题思路一:
反向遍历数组,从最后一个元素出发,然后从前往后查找哪个元素能跳到这个元素,一但查到,记录该元素的下标,跳跃次数+1,跳出本次查询
重复步骤1,不同的是每次从前往后找那个元素能跳到上一轮查找到的那个元素的下标,直至查找到第0位元素为止
复杂度分析一
时间复杂度: 对数组进行了双重遍历,因此时间复杂度为 ,其中 是数组 的长度
空间复杂度: 空间复杂度为
解题思路二:
正向遍历数组,计算查找出每次能跳的最远的距离,直至覆盖到最后一个元素,统计跳跃次数
复杂度分析一
时间复杂度: 对数组进行了一次遍历,因此时间复杂度为 ,其中 是数组 的长度
空间复杂度: 空间复杂度为
最后更新于