一道算法题-跳跃游戏 II

跳跃游戏 II

给你一个非负整数数组 nums ,你最初位于数组的第一个位置。

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。示例 2:

输入: nums = [2,3,0,1,4] 输出: 2

提示:

1 <= nums.length <= 104 0 <= nums[i] <= 1000

思路

代码位置为:https://github.com/shidawuhen/asap/blob/master/controller/algorithm/45-jump-game-ii.go

方案一:动态规划

分析

动态规划公式如下图所示:

一道算法题-跳跃游戏 II

举个例子,如果从位置0开始跳,因为值为7,所以可以选择跳到17的位置上,而且必然需要跳一次,那么只要选择17上,谁跳到最后一个位置用的跳跃次数最少即可。

按这个思路,使用递归,同时使用数组记录每个位置跳到最后位置最少跳跃次数即可。

时间复杂度的话,O(n*m),不是特别高效,不过好歹能过。

代码

var recordJump map[int]int

func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	recordJump = make(map[int]int, 0)
	recordJump[len(nums)-1] = 0
	return countJump(0, nums)
}

func countJump(index int, nums []int) int { //从index到末尾最短路径
	if index >= len(nums)-1 {
		return 0
	}
	minJump := 100000

	for i := 0; i < nums[index] && i+1+index < len(nums); i++ {
		j := 0
		if _, ok := recordJump[i+1+index]; ok {
			j = recordJump[i+1+index]
		} else {
			j = countJump(i+1+index, nums)
		}
		j = 1 + j
		if j < minJump {
			minJump = j
		}
	}

	recordJump[index] = minJump
	return minJump
}

方案二:动态规划

分析

方案一是从头到尾计算,我们完全可以改为从尾到头计算,因为后面计算出的每一个f(n)都是准确的,这样也无需递归计算。

代码

var recordJump map[int]int
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	recordJump = make(map[int]int, 0)
	recordJump[len(nums)-1] = 0
	for index := len(nums) - 2; index >= 0; index-- {
		//根据自身能跳跃的长度,找到最小值
		minJump := 1000000
		for i := index + 1; i < index+1+nums[index] && i < len(nums); i++ {
			jump := 1 + recordJump[i]
			if jump < minJump {
				minJump = jump
			}
		}
		recordJump[index] = minJump
	}
	return recordJump[0]
}

方案三:贪心

分析

贪心思路和方案一有点类似。其核心思路是,如果从0开始跳,最远能跳到7;下一跳的最远位置,必然是1~7上能跳到的最远位置;每次到达最远位置,意味多跳了一次。

贪心的效率是最高的,但是,也是比较难想到的。

代码

func jump3(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	maxPoint := 0
	targetPoint := nums[0]
	jump := 0
	for i := 0; i < len(nums); i++ {
		if i+nums[i] > maxPoint {
			maxPoint = i + nums[i]
		}
		if i == targetPoint || i == len(nums)-1 {
			jump++
			targetPoint = maxPoint
		}
	}
	return jump
}
上一篇:【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯


下一篇:LinkedList实现分析(二)——常用操作