面试经典题目：LeetCode55_跳跃游戏

题目描述

题目链接：leetcode55 跳跃游戏

递归法

要使用递归方法解决跳跃游戏问题，我们可以定义一个递归函数来检查从当前索引是否可以到达最后一个索引。

bool canJump(vector<int>& nums) {
    return helper(nums, 0);
}

bool helper(vector<int>& nums, int index) {
    // 如果已经到达最后一个下标，返回true
    if (index == nums.size() - 1) {
        return true;
    }
    // 如果当前下标的值为0且不是最后一个下标，返回false
    if (nums[index] == 0 && index != nums.size() - 1) {
        return false;
    }
    // 尝试从当前下标跳到每一个可能的下一个下标
    for (int i = 1; i <= nums[index]; ++i) {
        if (helper(nums, index + i)) {
            return true;
        }
    }
    return false;
}

解释

1. canJump 函数：

   • 这是主函数，它调用递归辅助函数 helper 来判断是否可以从第一个索引跳跃到最后一个索引。

2. helper 函数：

   • 基本情况：
     • 如果 index 等于数组长度减一（即最后一个索引），直接返回 true。
     • 如果 nums[index] 为 0 且 index 不是最后一个索引，则返回 false，因为无法从这里跳跃。
   • 递归情况：
     • 尝试从当前索引跳到每一个可能的下一个索引，并递归调用 helper 函数检查是否可以到达最后一个索引。

示例测试

• 示例 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 = [2, 3, 1, 1, 4] 的情况下，从索引 0 跳到索引 1 和从索引 1 跳到索引 2 都会重新计算。

2. 指数级增长的递归调用：

   • 每个位置都有可能跳到多个不同的位置，导致递归调用呈指数级增长。

优化

1. 记忆化递归（Memoization）：

   • 使用一个哈希表或数组来存储已经计算过的结果，避免重复计算。

2. 动态规划：

   • 使用动态规划来解决这个问题，可以显著减少计算量。

3. 贪心算法：

   • 使用贪心算法来提前终止不必要的递归分支。

使用记忆化递归

bool canJump(vector<int>& nums) {
    unordered_map<int, bool> memo;
    return helper(nums, 0, memo);
}

bool helper(vector<int>& nums, int index, unordered_map<int, bool>& memo) {
    // 如果已经到达最后一个下标，返回true
    if (index == nums.size() - 1) {
        return true;
    }
    // 如果当前下标的值为0且不是最后一个下标，返回false
    if (nums[index] == 0 && index != nums.size() - 1) {
        return false;
    }
    // 如果已经计算过该索引的结果，直接返回
    if (memo.find(index) != memo.end()) {
        return memo[index];
    }
    // 尝试从当前下标跳到每一个可能的下一个下标
    for (int i = 1; i <= nums[index]; ++i) {
        if (helper(nums, index + i, memo)) {
            memo[index] = true;
            return true;
        }
    }
    memo[index] = false;
    return false;
}

解释

1. 记忆化递归：
   • 使用 unordered_map<int, bool> 来存储已经计算过的结果。
   • 在每次递归调用之前，检查是否已经计算过该索引的结果，如果已经计算过，则直接返回结果。

使用动态规划

bool canJump(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n, false);
    dp[0] = true; // 初始位置总是可达的

    for (int i = 0; i < n; ++i) {
        if (dp[i]) {
            for (int j = 1; j <= nums[i] && i + j < n; ++j) {
                dp[i + j] = true;
            }
        }
    }

    return dp[n - 1];
}

解释

1. 动态规划：
   • 使用一个布尔数组 dp 来记录每个位置是否可达。
   • 初始化 dp[0] 为 true，表示初始位置总是可达的。
   • 从左到右遍历数组，如果当前位置可达，则更新其后所有可达的位置。

使用贪心

思路：

• 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
• 对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
• 如果最远距离已经超过了整个数组长度，那么此方案一定是成功的

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxlen = 0; // 初始化最大能到达的位置为0
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxlen) 
                return false; // 如果当前位置大于能到达的最远距离，则返回false
            maxlen = max(maxlen, i + nums[i]); // 更新最大能到达的位置
            if (maxlen >= nums.size() - 1) 
                return true; // 如果最大能到达的位置已经超过了最后一个下标，则返回true
        }
        return false; // 如果遍历完数组仍未到达最后一个下标，则返回false
    }
};

解析

示例 1: nums = [2, 3, 1, 1, 4]

• 初始状态：maxlen = 0
• i = 0：
  • maxlen = max(0, 0 + 2) = 2
• i = 1：
  • maxlen = max(2, 1 + 3) = 4
  • maxlen >= 4，返回 true

示例 2: nums = [3, 2, 1, 0, 4]

• 初始状态：maxlen = 0
• i = 0：
  • maxlen = max(0, 0 + 3) = 3
• i = 1：
  • maxlen = max(3, 1 + 2) = 3
• i = 2：
  • maxlen = max(3, 2 + 1) = 3
• i = 3：
  • maxlen = max(3, 3 + 0) = 3
  • i > maxlen，返回 false

优点

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

总结

这种方法通过贪心策略高效地解决了问题，避免了递归和动态规划中的大量重复计算，从而显著提高了性能。