时间轴

2025-10-02

init

题目：

P55 跳跃游戏

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

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

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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));
}

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

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_jump = 0;
        for(int i = 0;i<=max_jump && i < nums.size();i++)
            max_jump = std::max(max_jump, i+nums[i]);
            
        return (max_jump>= nums.size()-1);
    }
};

这题也可以用动态规划，时间复杂度O(n^2)
dp[i] = true 表示能到达i, dp[i] = false 表示不能到达i
那么对于位置i，如果存在j( 0 <= j < i )能到达，并且j出发的最大跳跃距离能覆盖i，即：

1
2
3
4
5
if(j+nums[j]>=i){
  dp[j] = true;
}else{
  dp[j] = false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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];
    }
};