跳跃游戏 II解题思路详解

题解跳跃游戏 II

- 🤚我的博客
- 🥛前言
跳跃游戏 II
- 描述
- 示例
- 提示
题解
- 初步思考
- 思路细节
- 代码实现
- 完整代码
END
- 💠END
- - 🏕️公众号

🤚我的博客

欢迎光临我的博客：https://blog.csdn.net/qq_52434217?type=blog

🥛前言

最近有点忙，然后调整了刷题思路，打算按照题型刷题，先从动态规划入手。

跳跃游戏 II

描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例

示例 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
题目保证可以到达 nums[n-1]

题解

初步思考

根据题目描述，在下标为i时的最大跳数为nums[i]，那么在i处能够跳的最远距离为i+nums[i]。

例如在示例1中，从下标为0开始，最大跳数为2，那么可以跳到i=1，然后再跳动nums[1]次即可到达i=4处。

想必各位都能想到这一步，但是如何将这个思路转化成代码表达出来呢?

思路细节

首先，肯定是从i=0开始跳，且最大跳数为nums[0]，例如示例一中的2。

接下来就需要在i=1和i=2中找到最大的跳数。为什么呢？我们只需要保证在当前最大跳数内找到下一次的最大跳数即可。以示例一为例，在i=0时，我们跳1步也可，跳2步也可。那么如果我们跳1步，则到达i=1的位置，这时我们的最大跳数为nums[1]=3，当我们选择直接跳跃3步时，就可以到达n-1=4的位置。而如果我们选择在i=0处跳跃2步时，则到达i=2的位置，此时能够跳的最大跳数为1。

如果继续按照i=2的位置进行跳跃，那么就可以跳到i=3的位置，这个位置在第二次最大跳跃数范围内。也就是与i=1时向前跳跃2步的情况相同，可以不用再考虑。

那么如何增加跳跃的次数呢？根据上面的分析，无论是在i=2向前跳1步还是在i=1处向前跳2步都是一种情况，也就是只要当前位置跳跃的步数没有超过最大跳跃步数都可以视为当前跳跃次数。那么我们就能使用一个变量，保存最大跳跃的位置，当遍历的i值超过这个最大跳跃位置就对跳跃次数加一

代码实现

根据上面的思路细节，将思路转化成代码

首先需要找到最大的跳数和最大跳跃位置，在i处的最大跳跃次数为nums[i]那么能够跳跃的最大位置是nums[i]+i，而我们是需要找到第x次跳跃时的最大跳跃步数和位置。所以代码如下

maxPos = max(nums[i]+i,maxPos)

以示例一为例，无论i=0处跳到nums[1]还是nums[2]，最大跳数都是一样的。具体功能可以参考下面的图

要知道跳跃到的位置i属于第几次跳跃，需要设置一个end下标，当跳跃的位置i=end时，就对跳跃次数加一，并且更新下一次的end位置为maxPos。end初始化为0。随后的end则是maxPos的位置。

if i == end:
	end = maxPos
	res += 1

完整代码

python版本

class Solution:
	def jump(self,nums):
	res = 0
	end,maxPos = 0,0
	for i in range(len(nums)-1):
		maxPos = max(nums[i]+i,maxPos)
		
		if i == end:
			end = maxPos
			res += 1
	return res

java版本

class Solution{
	public int jump(int[] nums){
		int res=0,end=0,maxPos=0;
		for(int i =0;i<nums.length-1;i++){
			int pos = nums[i]+i;
			maxPos = pos>maxPos?pos:maxPos;
			if(i==end){
				end = maxPos;
				res++;
			}
		}
		return res;
	}
}