⭐算法OJ⭐跳跃游戏【贪心算法】（C++实现）Jump Game 系列 I,II

既股票买卖系列之后的第二组贪心算法题目：跳跃游戏系列。这一篇介绍的两个问题，其输入均为一个数组，每个元素表示在该位置可以跳跃的最大长度。

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

问题描述

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

贪心策略

• 维护一个最远可到达的位置 max_reach。
• 遍历数组，更新 max_reach。
• 如果 max_reach 超过最后一个下标，则返回 True。

解题思路

这是一个典型的贪心算法问题。我们可以通过维护一个变量 max_reach 来记录当前能够到达的最远位置。遍历数组时，更新 max_reach，并检查是否能够到达或超过最后一个下标。

步骤

• 初始化 max_reach = 0，表示当前能够到达的最远位置。
• 遍历数组 nums：
  • 如果当前位置 i 超过了 max_reach，说明无法到达当前位置，返回 false。
  • 更新 max_reach 为 max(max_reach, i + nums[i])。
  • 如果 max_reach 已经大于或等于最后一个下标，返回 true。
• 遍历结束后，如果 max_reach 大于或等于最后一个下标，返回 true，否则返回 false。

bool canJump(vector<int>& nums) {int max_reach = 0;for (int i = 0; i < nums.size(); i++) {if (max_reach < i) {return false;}max_reach = max(max_reach, i + nums[i]);if (max_reach >= nums.size() - 1) {return true;}}if (max_reach >= nums.size() - 1) {return true;}else {return false;}
}

复杂度分析

• 时间复杂度：只需要遍历数组一次，时间复杂度为 $O(n)$，其中 $n$ 是数组的长度。
• 空间复杂度：只使用了常数级别的额外空间，空间复杂度为 $O(1)$。

45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

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

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

解题思路

这是一个典型的贪心算法问题。我们需要找到到达最后一个下标的最小跳跃次数。可以通过维护两个变量来解决：

• 当前跳跃范围：[start, end]，表示当前跳跃可以到达的范围。
• 最远可到达位置：max_reach，表示在当前跳跃范围内，能够到达的最远位置。

步骤

• 初始化：
  • jumps = 0：记录跳跃次数。
  • end = 0：当前跳跃范围的结束位置。
  • max_reach = 0：当前跳跃范围内能够到达的最远位置。
• 遍历数组 nums：
  • 更新 max_reach 为 max(max_reach, i + nums[i])。
  • 如果当前位置 i 到达了当前跳跃范围的结束位置 end：
    • 增加跳跃次数 jumps++。
    • 更新 end 为 max_reach，表示进入下一个跳跃范围。
• 返回 jumps。

int jump(vector<int>& nums) {int jumps = 0;      // 记录跳跃次数int end = 0;        // 当前跳跃范围的结束位置int max_reach = 0;  // 当前跳跃范围内能够到达的最远位置for (int i = 0; i < nums.size() - 1; i++) {max_reach = max(max_reach, i + nums[i]);// 如果当前位置到达了当前跳跃范围的结束位置if (i == end) {jumps++;       // 增加跳跃次数end = max_reach; // 更新跳跃范围}}return jumps;
}

复杂度分析

• 时间复杂度：只需要遍历数组一次，时间复杂度为 $O(n)$，其中 $n$ 是数组的长度。
• 空间复杂度：只使用了常数级别的额外空间，空间复杂度为 $O(1)$。