Jump Game

题目描述

跳跃游戏

给定一个非负整数，最初位于整数的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。

请判断能否到达最后一个位置。

示例：

输入：[2, 3, 1, 1, 4]
输出：true

解法

解法一：DFS

从最后一个位置开始倒推。

• 时间复杂度：O(N)

• 空间复杂度：O(N)

func canJump(nums []int) bool {
    visited := make([]bool, len(nums))
    return helper(nums, 1, visited)
}

func helper(nums []int, end int, visited []bool) bool {
    if end == len(nums) {
        return true
    }

    distance := 0
    for i := len(nums) - 1 - end; i >= 0; i-- {
        distance++
        if visited[i] {
            continue
        }
        if distance > nums[i] {
            continue
        }
        if helper(nums, distance+end, visited) {
            return true
        }
        visited[i] = true
    }
    return false
}

解法二：贪心

• 时间复杂度：O(N)

• 空间复杂度：O(1)

func canJump(nums []int) bool {
    remote := 0

    for i := 0; i <= remote; i++ {
        if remote < nums[i] + i {
            remote = nums[i] + i
        }
        if remote >= len(nums) - 1 {
            return true
        }
    }

    return false
}