面试经典150题 P55 跳跃游戏

---

时间轴

时间轴

2025-10-02

init

贪心，栈或队列，动态规划

---

题目：

P55 跳跃游戏

https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

我最先想到的是用队列遍历，BFS 解法，用栈应该也行，可以看到这个复杂度相当大。

#include <queue>
#include <unordered_set>
#include <vector>

using std::queue;
using std::unordered_set;
using std::vector;

class Solution {
    public:
        bool canJump(vector<int> &nums)
        {
                int n = nums.size();
                int jmp;
                int curr;
                int i, tmp;
                queue<int> que;
                unordered_set<int> uset;
                if (n == 1) {
                        return true;
                }

                que.push(0);
                uset.insert(0);
                do {
                        curr = que.front();
                        jmp = nums[curr];
                        if (jmp == 0) {
                                que.pop();
                                uset.erase(curr);
                                continue;
                        }

                        for (i = 1; i <= jmp; i++) {
                                tmp = curr + i;
                                if (tmp == n - 1) {
                                        return true;
                                } else if (tmp < n && uset.count(tmp) == 0) {
                                        que.push(tmp);
                                        uset.insert(tmp);
                                }
                        }
                        uset.erase(curr);
                        que.pop();

                } while (!que.empty());

                return false;
        }
};

#include <stdio.h>
int main()
{
        Solution S;
        vector<int> vec = { 2, 5, 0, 0 };
        printf("%d\n", S.canJump(vec));
}

看了评论有一个解法很有趣，采用贪心策略，不用想具体过程，能跳多远就跳多远，如果跳过了最后的位置之后，那么必定能跳到最后位置。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i, n = nums.size();
        int max_reach_pos = 0;

        for( i = 0; i < n && i <= max_reach_pos; i++ ){
            max_reach_pos = std::max(max_reach_pos, i + nums[i]);
        }

        return (max_reach_pos >= n-1);

    }
};

这题也可以用动态规划，时间复杂度 O(n^2)

• dp[i] = true表示能到达 i,
• dp[i] = false表示不能到达 i

那么对于位置 i，如果存在 j( 0 <= j < i )能到达，并且 j 出发的最大跳跃距离能覆盖 i，即：

if(j+nums[j]>=i){
  dp[j] = true;
}else{
  dp[j] = false;
}

#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n, false);
        dp[0] = true;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;  // 只要能到达，就不用再继续找
                }
            }
        }

        return dp[n-1];
    }
};

leetcode hot 100 rewrite, 贪心策略

#include <vector>
using std::vector;

class Solution {
    public:
        bool canJump(vector<int> &nums)
        {
                int i, n = nums.size();
                int max_reach = 0;

                for (i = 0; i < n && i <= max_reach; i++) {
                        max_reach = std::max(max_reach, i + nums[i]);
                        if (max_reach >= n - 1)
                                return true;
                }

                return false;
        }
};