打开转盘锁 图解题解

这道题到底在问什么

deadends

["0201","0101","0102","1212","2002"]

target

"0202"

输出

6

最优解：一步一步想明白

1. 3换个眼光:每个密码是地图上的一个点,能一步互拨的两个密码之间有条路。于是「最少拨几下」=「图上从 0000 到 0202 最短走几步」。
2. 4为什么不乱走或 DFS?乱走会绕远,DFS 一头扎到底找到的也未必最短。BFS 严格按层扩,第一次扩到目标的圈数就是答案。
3. 5下面开始一帧一帧演 BFS:盯住当前扩展的状态、它生成的8 个邻居、谁被 dead/visited 筛掉、队列怎么长、层数(步数)怎么涨。
4. 6queue=[0000],步数 0起跑线:把 0000 入队,标进 visited,记它是第 0 层(拨 0 下就在这)。点位先空着,下面看它怎么裂出邻居。若 0000 本身就是死亡数字,直接返回 -1。
5. 7每位 +1/−1,共 8 个把 0000 出队,生成 8 个邻居:每一位分别 +1 或 −1(个位 0−1 绕回 9)。它们都不在死亡集、也没来过,全部入队并标记为第 1 层。
6. 88 个全标记,无 target第 1 层这 8 个都进 visited 了(变深),里面没有 target(0202)。所以答案不是 1。纪律:同一层全处理完,才进下一层。
7. 91000 出队,生成它的邻居轮到第 1 层的 1000 出队,生成它的邻居。其中 1100(百位+1)把我们带向「1 开头」,正是绕开死亡数字 0201/0101/0102 的关键岔路。回到 0000 的那格已 visited、被跳过。
8. 101100 等入队,标 visited第 2 层这批新邻居全部记进 visited。BFS 不挑不选,谁也不漏。仍没碰到 target,继续往外扩第 3 层。1100 这格是后面活路的关键落点。
9. 110100 出队,邻居含死亡数字再扩第 1 层的 0100。它的邻居 0101 是死亡数字,直接丢弃;1100、0000 已 visited 跳过。剩下的活邻居(0200/0110/…)入第 2 层。可见每条岔路都要过一遍筛子。
10. 120202 周围被死亡数字封死看似 0000→0200→0202 很近,但从 0200 拨到 0202 必经 0201(死亡数字),另一头挨着的 0102 也是死亡数字,这条近路被封死。BFS 会自动绕开,去找另一条活路——这正是 dead 集的价值。
11. 131100 出队,生成邻居扩展第 2 层的 1100,生成邻居。其中 1200(百位 1→2)继续朝 0202 靠;0100 和 1000 已 visited、跳过。新邻居入第 3 层队列。
12. 141200 出队,生成邻居扩展第 3 层的 1200,生成邻居。其中 1201(个位 0→1)是通往目标的下一跳;1100 已 visited。把新邻居纳入第 4 层。
13. 151201 出队,生成邻居扩展第 4 层的 1201。注意它的一个邻居 0201 是死亡数字,直接丢弃;1200 已 visited 跳过。活下来的 1202(个位 1→2)入第 5 层——离目标只差千位了。
14. 161202 出队,生成邻居扩展第 5 层的 1202。把千位从 1 拨回 0,得到 0202!它不在 dead、也没 visited,入队为第 6 层。旁边的 1212 是死亡数字被丢弃,1201 已 visited。
15. 170202 出队 == target0202 在第 6 层第一次被扩到——它就是 target!这一层的步数 6 就是答案。BFS 第一次碰到目标即最短,立刻收工。
16. 180000→1000(千位 0→1)回放这条活路:从 0000 出发,把千位拨到 1,得到 1000(第 1 步)。一跳只动一位。
17. 191000→1100(百位 0→1)接着把百位拨到 1,得到 1100(第 2 步)。这一跳把我们带向「1 开头」,正是绕开 0200 那边死亡数字的关键。
18. 201100→1200→1201继续:1100 百位拨到 2 得 1200(第3步),个位拨到 1 得 1201(第4步)。路径一格格点亮,绕过了挡在 0200 那边的死亡数字。
19. 211201→1202(个位 1→2)把个位从 1 拨到 2,得到 1202(第 5 步)。现在只差千位的那个 1 还没归零,离 0202 只剩最后一跳。
20. 221202→0202 ✓ = target最后把千位拨回 0,得到 0202(第 6 步)。整条路 0000→1000→1100→1200→1201→1202→0202 共 6 步,每跳只动一位、个个都活着——这就是 BFS 给的最优解。
21. 23层数 = 步数,越扩越大整体看 BFS 就是水波一圈圈往外:第 0 层 1 个、第 1 层 8 个、之后每层把所有新邻居纳入。圈数就是步数,第 6 圈第一次碰到 0202,答案锁定为 6。
22. 270000 个位 −1 → 0009演示个位的环形:0000 的个位是 0,−1 不是 −1,而是绕回 9 得 0009;+1 得 0001。这就是 (x+9)%10 在干的事——转盘首尾相接。
23. 280100 被多个父节点重复入队若只在出队时才标 visited,同一个 0100 会被多个邻居反复塞进队列,队列爆炸还重复扩展。正确做法:生成时就标 visited,让每个状态只进队一次。

⚠️ 容易写错的地方

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

from collections import deque
def openLock(deadends, target):
    dead = set(deadends)
    if '0000' in dead: return -1
    if target == '0000': return 0
    visited = {'0000'}
    q = deque([('0000', 0)])
    while q:
        s, d = q.popleft()
        if s == target: return d
        for i in range(4):
            x = int(s[i])
            for nx in ((x + 1) % 10, (x + 9) % 10):
                t = s[:i] + str(nx) + s[i+1:]
                if t not in visited and t not in dead:
                    visited.add(t)
                    q.append((t, d + 1))
    return -1

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        if (dead.count("0000")) return -1;
        if (target == "0000") return 0;
        unordered_set<string> visited{"0000"};
        queue<pair<string,int>> q;
        q.push({"0000", 0});
        while (!q.empty()) {
            auto [s, d] = q.front(); q.pop();
            if (s == target) return d;
            for (int i = 0; i < 4; ++i) {
                int x = s[i] - '0';
                for (int nx : {(x + 1) % 10, (x + 9) % 10}) {
                    string t = s; t[i] = char('0' + nx);
                    if (!visited.count(t) && !dead.count(t)) {
                        visited.insert(t);
                        q.push({t, d + 1});
                    }
                }
            }
        }
        return -1;
    }
};

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        if (dead.contains("0000")) return -1;
        if (target.equals("0000")) return 0;
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        Deque<String> q = new ArrayDeque<>();
        q.offer("0000");
        int d = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                String s = q.poll();
                if (s.equals(target)) return d;
                for (int i = 0; i < 4; i++) {
                    int x = s.charAt(i) - '0';
                    int[] cand = {(x + 1) % 10, (x + 9) % 10};
                    for (int nx : cand) {
                        char[] arr = s.toCharArray();
                        arr[i] = (char) ('0' + nx);
                        String t = new String(arr);
                        if (!visited.contains(t) && !dead.contains(t)) {
                            visited.add(t);
                            q.offer(t);
                        }
                    }
                }
            }
            d++;
        }
        return -1;
    }
}

复杂度

面试官可能追问