跳跃游戏 III 图解题解

这道题到底在问什么

输入

arr=[4,2,3,0,3,1,2], start=5

输出

true(5→4→1→3,arr[3]=0)

输入

arr=[3,0,2,1,2], start=2

输出

false(怎么跳都落不到值为 0 的下标)

最优解：一步一步想明白

1. 3记住「下标当节点、i±arr[i] 是两条边、seen 防重、BFS 找值为 0 的下标」,下面逐帧套它。
2. 4从起点下标 5(紫)出发:标记为已访问(蓝)、放进队列。目标是落到某个值为 0 的下标——这张数组里 arr[3]=0,就是我们要找的终点。
3. 5队首弹出下标 5(紫),值 arr[5] = 1,不是 0。看它能往两个方向跳:向右 5 + 1,向左 5 − 1。
4. 6先算向右的落点:5 + 1 = 6。再看下标 6 能不能落脚。
5. 7下标 6 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
6. 8先算向左的落点:5 − 1 = 4。再看下标 4 能不能落脚。
7. 9下标 4 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
8. 10队首弹出下标 6(紫),值 arr[6] = 2,不是 0。看它能往两个方向跳:向右 6 + 2,向左 6 − 2。
9. 11先算向右的落点:6 + 2 = 8。再看下标 8 能不能落脚。
10. 12下标 8 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
11. 13先算向左的落点:6 − 2 = 4。再看下标 4 能不能落脚。
12. 14下标 4(蓝)之前已经访问过了,BFS 不重复入队、直接跳过 —— 这正是 seen 数组的作用:挡住「跳过去又跳回来」的死循环。
13. 15队首弹出下标 4(紫),值 arr[4] = 3,不是 0。看它能往两个方向跳:向右 4 + 3,向左 4 − 3。
14. 16先算向右的落点:4 + 3 = 7。再看下标 7 能不能落脚。
15. 17下标 7 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
16. 18先算向左的落点:4 − 3 = 1。再看下标 1 能不能落脚。
17. 19下标 1 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
18. 20队首弹出下标 1(紫),值 arr[1] = 2,不是 0。看它能往两个方向跳:向右 1 + 2,向左 1 − 2。
19. 21先算向右的落点:1 + 2 = 3。再看下标 3 能不能落脚。
20. 22下标 3 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
21. 23先算向左的落点:1 − 2 = -1。再看下标 -1 能不能落脚。
22. 24下标 -1 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
23. 25队首弹出下标 3(绿):它的值 arr[3] = 0 —— 命中目标!BFS 成功跳到了值为 0 的下标,答案 true。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        seen = [False] * n
        q = deque([start])
        seen[start] = True
        while q:
            i = q.popleft()
            if arr[i] == 0:
                return True
            for j in (i + arr[i], i - arr[i]):
                if 0 <= j < n and not seen[j]:
                    seen[j] = True
                    q.append(j)
        return False

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<int> seen(n);
        queue<int> q;
        q.push(start); seen[start] = 1;
        while (!q.empty()) {
            int i = q.front(); q.pop();
            if (arr[i] == 0) return true;
            for (int j : {i + arr[i], i - arr[i]}) if (j >= 0 && j < n && !seen[j]) {
                seen[j] = 1; q.push(j);
            }
        }
        return false;
    }
};

import java.util.*;
class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] seen = new boolean[arr.length];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start); seen[start] = true;
        while (!q.isEmpty()) {
            int i = q.poll();
            if (arr[i] == 0) return true;
            int a = i + arr[i], b = i - arr[i];
            if (a >= 0 && a < arr.length && !seen[a]) { seen[a] = true; q.offer(a); }
            if (b >= 0 && b < arr.length && !seen[b]) { seen[b] = true; q.offer(b); }
        }
        return false;
    }
}

复杂度

面试官可能追问