跳跃游戏

1. 题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标

2. 思路

1. 思路一
   • 暴力DFS
   • 当前索引从0开始，尝试让当前索引加上0...nums[index]
   • 是否能超过len(nums)
2. 思路二
   • 最远位置

3. 实现

3.1. 暴力DFS

func canJump(nums []int) bool {
    return canJumpDFS(nums, 0)
}

func canJumpDFS(nums []int, index int) bool {
    if index >= len(nums) -1 {
        return true
    }
    steps := nums[index]
    if steps == 0 {
        return false
    }

    for i := steps; i > 0; i-- {
        if canJumpDFS(nums, index+i) {
            return true
        }
    }

    return false
}

3.2. 最远位置

func canJump2(nums []int) bool {
	//初始化当前能到达最远的位置
	maxIndex := 0
	//i为当前位置，step是当前位置的跳数
	index := 0
	step := 0
	for index, step = range nums {
		//如果当前位置能到达，并且当前位置+跳数>最远位置
		nextMaxIndex := index + step
		if maxIndex >= index && nextMaxIndex > maxIndex {
			//更新最远能到达位置
			maxIndex = nextMaxIndex
		}
	}

	return maxIndex >= index
}

4. 参考

• 55. 跳跃游戏 - 力扣（LeetCode）