【笔试高频考点】LeetCode跳跃游戏系列，持续更新！

前言：

跳跃游戏 涉及到一些常用算法，比如贪心算法、广度优先搜索等，属于LeetCode题库中的中等题和难题，也是大厂笔试中常考的题型之一。

一、跳跃游戏1

题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：
1 <= nums.length <= 3*10^4
0 <= nums[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

解析

解题思路：从左往右遍历数组nums，在每一个位置上能到达的最远距离是：nums[i]+i 。当能跳跃到的最远距离 max_reach > nums.size()-1 时，即返回true；

class Solution {
public: bool canJump(vector<int>& nums) { // 初始化到达最远的索引位置 int max_reach = 0; for(int i=0; i<nums.size(); ++i) { if(i<=max_reach) { // 更新能到达最远的索引位置 max_reach = max(i+nums[i], max_reach); // 如果最大位置索引超过最后元素的索引值，则能到达；如果没有，继续下一个元素 if(max_reach >=nums.size()-1) return true; } else return false; } return false; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

二、跳跃游戏2

题目

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:
输入: [2,3,1,1,4]
输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

解析

解题思路：这题是一道典型的贪心算法题，要使得跳跃次数最少，则每次应该追求跳跃最远的路径。于是就有两种选择：(1) 从左往右跳跃进行推算 (2) 从右边（结尾）到左边（开始）推算。 我们就以第二种方法为例：找出每次能跳到结尾位置的最左边的索引位置n，下一次再以n为末尾位置，继续同样的操作，直到n=0，结束。

class Solution {
public: int jump(vector<int>& nums) { int count = 0; // 记录跳跃次数 int n=nums.size()-1; //当前的最远跳跃索引 while(n>0) { // 从前向后找，找到第一个能达到末尾的索引位置 for(int i=0; i<n; ++i) { if(nums[i]+i>=n) { n = i; //找到了将该索引值计入n，作为下一次的终点索引 count += 1; //每找到一次，计数加1 break; } } } return count; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

三、跳跃游戏3

题目

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，
你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 

示例 2：
输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3：
输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。 提示：
1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

解析

解题思路：数组arr长度是有限的，所以在数轮后，肯定会跳到重复位置上的情况。为了避免重复位置上的计算，所以需要提前创建一个数组used，表示已经跳到过的位置，并置1，下次不进行计算。对于没有跳到的位置（i-arr[i]或i+arr[i]）将其存入队列q中，这样再之后可以一一按照顺序进行判断，直到出现0元素结束程序，返回true；或者，且此时数组位置均遍历到，q中元素皆已判断完，且不存在0元素，程序结束，返回false。

class Solution {
public: bool canReach(vector<int>& arr, int start) { if(arr[start]==0) return true;   //当第一个元素为0时，直接判断成立 int n = arr.size(); vector<int> used(n); //走过的元素位置置1 used[start] = true; //第一个元素占据的位置置1 queue<int> q; //存放数组索引 q.push(start); while(q.size()>0) { int i = q.front(); //取队列的首元素 q.pop(); //删掉已经处理过的索引 int left = i-arr[i]; //左索引 int right = i+arr[i]; //右索引 // 判断往左跳的情况 if(left>=0 && !used[left]) { if(arr[left]==0) return true; q.push(left); used[left] = true; } // 判断往右跳的情况 if(right<n && !used[right]) { if(arr[right]==0) return true; q.push(right); used[right] = true; } } return false; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/116075336