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

一时失言乱红尘 2023-01-16 04:48 138阅读 0赞

**前言：**

**跳跃游戏** 涉及到一些常用算法，比如贪心算法、广度优先搜索等，属于LeetCode题库中的中等题和难题，也是大厂笔试中常考的题型之一。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

--------------------

## 一、跳跃游戏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
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 解析 ###

**解题思路**：从左往右遍历数组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;
        }
    };

--------------------

## 二、跳跃游戏2 ##

### 题目 ###

给定一个非负整数数组，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    
    示例:
    输入: [2,3,1,1,4]
    输出: 2
    
    解释: 跳到最后一个位置的最小跳跃数是 2。
         从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
    
    说明:
    假设你总是可以到达数组的最后一个位置。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/jump-game-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 解析 ###

**解题思路：这题是一道典型的贪心算法题**，要使得跳跃次数最少，则每次应该追求跳跃最远的路径。于是就有两种选择：(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;
        }
    };

--------------------

## 三、跳跃游戏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
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 解析 ###

解题思路：数组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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221022/cf1508ba60e840ab9189f655a11ee774.png