跳跃游戏
题目链接: https://leetcode.cn/problems/jump-game
解题思路:
正向遍历:从头开始遍历,用一个遍历记录我们能够跳到的最远距离,逐步更新最远距离,若能到达目标位置,即为成功
反向遍历:若一个点能到达目标节点,将其更新为目标节点,若最终目标节点为起点,说明可以从起点跳到终点
//正向遍历
func canJump1(nums []int) bool {
maxStep := 0
n := len(nums)
if n == 1{
return true
}
for k,v := range nums {
if maxStep >= k && k+v>maxStep {
maxStep = k+v
}
}
return maxStep >=n-1
}
//反向遍历
func canJump(nums []int) bool {
n := len(nums)
if n == 1{
return true
}
maxStep := n-1
for i:=n-2;i>=0;i-- {
if nums[i]+i >= maxStep {
maxStep =i
}
}
return maxStep == 0
}
复杂度分析
时间复杂度: 只遍历了一遍数组 ,因此时间复杂度为 ,其中 是数组 的长度
空间复杂度: 只使用了常数个变量,因此空间复杂度为 ,无论输入的数组 的长度如何,函数使用的空间都是固定的
最后更新于
这有帮助吗?