leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 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

思路

我们思考一种朴素的解法，就是从后往前遍历遍历所有点x，在这层循环中再从左往右遍历所有点，看看哪个点最先能到达x,这个点就是我们的下一个要达到的点，然后我们再从左往右寻找能到达这个点的点就ok

class Solution {public int jump(int[] nums) {int position = nums.length - 1;int steps = 0;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;steps++;break;}}}return steps;}
}

我们观察下每次跳跃的规律，就拿 $[2,3,1,2,4,2,3]$ 来说，

• 对于位置0而言，他可以跳到位置1，2上；
• 对于位置1而言，他可以跳到2，3，4这些位置上；
• 对于位置2而言，他可以跳到位置4上；

此时我们发现一件事，当我们遍历数组到位置2，即 [1] 的时候，此时跳跃者肯定会从 [3，1] 这个子数组中跳跃到更远的地方；我们记录这个更远的地方为end，当我们遍历到end的时候，跳跃者肯定会从 $[上一次跳跃的位置，end]$ 中一个地方往前跳，哪个点跳的远就从哪个点跳

不难发现，我们每次到达end点，其实之前或者此刻都跳了一次，我们记录这次跳跃。

在程序一开始的时候，只遍历的第一个点，所以只能从第一个点开始跳；

当遍历结束的时候，如果我们遍历第n个点，而此刻end又恰好是第n个点，因为end是上一次跳跃更新的，所以上一次跳跃我们就到达了n点，所以我们不遍历n点，以免多计算一次

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

class Solution:def jump(self, nums: List[int]) -> int:right = 0end = 0n = len(nums)cnt = 0for i in range(n-1):if right < i+nums[i]:right = i+nums[i]if end == i:cnt += 1end = rightreturn cnt