【小白爬Leetcode45】3.8 跳跃游戏II Jump GameII

题目discription中文描述 思路一 逆序法，时间复杂度O(n²)，空间复杂度O(1)思路二 正序法，时间复杂度O(n)，空间复杂度O(1) Leetcode 45 $medium$

点击进入原题链接：Leetcode 45 跳跃游戏II Jump GameII

这道题的前导：Leetcode 55 跳跃游戏 Jump Game

题目

discription

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example: Note: You can assume that you can always reach the last index.

中文描述

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

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

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

示例: 说明:

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

思路一 逆序法，时间复杂度O(n²)，空间复杂度O(1)

这道题的与55题medium难度的那个区别在于：

55题目只要求判断是否能到达终点，没有要求跳跃最少的次数，因此不需要优化路径；而这道题已知可以到达终点，找出最少的跳跃次数。

一个朴素的想法是：即然我已知可以到达末尾，那么我从末尾出发往回跳，有点像小时候玩迷宫游戏我妈妈教我从终点出发一样。

从最后一个点出发，遍历前面所有的元素，在可以到达目前位置（最后一个点）的元素中选择序号最小的（实际上就是往最前面的地方回跳），一次来达到最小步数。

由于每一步都要遍历前面的所有元素，因此最坏时间复杂度为O(n²)，遗憾的是，没有用到额外的容器存储，空间复杂度为O(1)。 遗憾的是，这种解法无法通过第90个例： emmm，满屏的1，第一遍遍历的时候要从倒数第二个1开始遍历到头，第二遍遍历的时候要从倒数第三个1开始遍历到头，时间显然是超了的.

思路二 正序法，时间复杂度O(n)，空间复杂度O(1)

这个想法也很朴素，就是每一步选择最有潜力那个元素，用的思想和我之前的博客里是一样的：这道题的前导：Leetcode 55 跳跃游戏 Jump Game

放上那篇文章的解释：

这里无非是在每一次往前跳的时候步数++而已。

class Solution { public: int jump(vector<int>& nums) { int i = 0; int steps = nums[0]; // 当前可跳的步数 int cnt = 0; while (i<nums.size()-1) { int largest_step = steps; int largets_pos = 0; for (int j = 1; j < steps + 1; j++) { if (i + j >= nums.size() - 1) {largets_pos = j;break;} // 如果已经能到终点，就不再遍历，否则数组会越界 if (largest_step <= j + nums[i + j]) { largest_step = j + nums[i + j]; largets_pos = j; } } i += largets_pos; steps = nums[i]; cnt++; } return cnt; } };

看了官方解答，果然更加简洁：

class Solution { public: int jump(vector<int>& nums) { int maxPos = 0, n = nums.size(), end = 0, step = 0; for (int i = 0; i < n - 1; ++i) { //i<n-1是因为不需要访问最后一个元素，不然会多一次跳跃 if (maxPos >= i) { maxPos = max(maxPos, i + nums[i]); if (i == end) { end = maxPos; ++step; } } } return step; } };