LeetCode 752. 打开转盘锁

2024-10-18 HGNULB 约 7 分钟

文章信息 9 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节微软拼多多快手

题目描述

✅ 752. 打开转盘锁

题意分析

从四位状态 0000 出发，每次选择一个拨轮向上或向下转一格，数字在 0 到 9 之间循环。求到达 target 的最少操作次数，不能经过死亡状态；无法到达则返回 -1。死亡状态可能迫使路径绕行，不能只把四个拨轮各自的最少步数相加。

解法：BFS 按层扩展状态

核心思路

[!blue]

把四位字符串看作图中的节点，一次合法转动连接两个节点，死亡状态视为不能进入的节点。每条边都恰好需要一次操作，因此用 BFS 从 0000 按距离从小到大搜索，不必预先建立整张图。

step 表示当前层的最少操作次数。每层开始固定队列长度 size，只取出这 size 个状态，它们产生的新邻居留到下一层，整层结束后才令 step 加一。如果某个新状态能用更少步数到达，它应当已在前面的层中被发现；所以首次发现就是最短路径，出队遇到目标时直接返回 step。

visited 在入队时标记状态。同一个状态无论经哪条路径到达，后续能做的操作都一样，而首次到达已经最短，因此无需再次入队；这也能阻止拨轮来回转动造成循环。

每个状态有四个拨轮、每个拨轮有两个转动方向，共 8 个邻居。两个方向都必须从该位保存的 original 生成；生成后恢复这一位，再处理下一位，保证每个邻居只改变一个拨轮。

先排除起点本身是死亡状态的情况，再把它作为第 0 层入队。目标若就是 0000，第一次出队即返回 0；若队列耗尽，所有可达的非死亡状态都已检查，仍未找到目标就返回 -1。

解题步骤

将所有死亡状态加入哈希集合，先检查 0000 是否被封锁。

将 0000 入队并立即加入访问集合，令 step = 0。

每轮记录当前队列长度 size，只处理这 size 个同层状态。

出队状态若等于 target，立即返回 step。

对四个拨轮分别生成向上、向下转一格的 8 个邻居；9 向上回到 0，0 向下回到 9。

跳过死亡或已访问状态，其余状态在入队时立刻标记。

当前层处理完后执行 step++；队列耗尽仍未命中则返回 -1。

代码实现

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>();

        for (String state : deadends) {
            dead.add(state);
        }

        if (dead.contains("0000")) {
            return -1;
        }

        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();

        queue.offer("0000");
        visited.add("0000");

        int step = 0;

        while (!queue.isEmpty()) {
            // 本层状态都使用相同操作次数，新邻居留到下一层。
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String current = queue.poll();

                if (current.equals(target)) {
                    return step;
                }

                for (String next : nextStates(current)) {
                    if (dead.contains(next) || !visited.add(next)) {
                        continue;
                    }

                    queue.offer(next);
                }
            }

            step++;
        }

        return -1;
    }

    private List<String> nextStates(String state) {
        List<String> next = new ArrayList<>(8);
        char[] digits = state.toCharArray();

        for (int i = 0; i < 4; i++) {
            // 上下两种转动都从这一原始数字生成，不能在上转结果上再减一。
            char original = digits[i];

            digits[i] = original == '9' ? '0' : (char) (original + 1);
            next.add(new String(digits));

            digits[i] = original == '0' ? '9' : (char) (original - 1);
            next.add(new String(digits));

            // 恢复这一位后再修改其他拨轮，保证一次只动一位。
            digits[i] = original;
        }

        return next;
    }
}

func openLock(deadends []string, target string) int {
    dead := make(map[string]bool, len(deadends))
    for _, state := range deadends {
        dead[state] = true
    }
    if dead["0000"] {
        return -1
    }

    queue := []string{
        "0000",
    }
    visited := map[string]bool{"0000": true}
    step := 0

    for len(queue) > 0 {
        // 本层状态都使用相同操作次数，新邻居留到下一层。
        size := len(queue)
        for i := 0; i < size; i++ {
            current := queue[0]
            queue = queue[1:]
            if current == target {
                return step
            }

            for _, next := range nextLockStates(current) {
                if dead[next] || visited[next] {
                    continue
                }
                visited[next] = true
                queue = append(queue, next)
            }
        }
        step++
    }
    return -1
}

func nextLockStates(state string) []string {
    next := make([]string, 0, 8)
    digits := []byte(state)

    // 每次只修改一个拨轮，生成两个邻居后恢复原数字。
    for i := 0; i < 4; i++ {
        // 上下两种转动都从这一原始数字生成，不能在上转结果上再减一。
        original := digits[i]

        if original == '9' {
            digits[i] = '0'
        } else {
            digits[i] = original + 1
        }
        next = append(next, string(digits))

        if original == '0' {
            digits[i] = '9'
        } else {
            digits[i] = original - 1
        }
        next = append(next, string(digits))

        digits[i] = original
    }
    return next
}

复杂度分析

设死亡状态数为 D，状态图中最多有 V = 10^4 个状态，每个状态最多连接 8 个邻居。

时间复杂度：$O(D + V)$。先建立死亡集合，每个可达状态最多入队一次，生成邻居的数量和字符串长度都是常数。

空间复杂度：$O(D + V)$。死亡集合保存禁用状态，队列和访问集合最多保存全部可达状态。

关键点总结

[!green]

边权全部为 1，BFS 的层数天然就是最少拨动次数。

死亡状态不能入队；起点是死亡状态必须单独特判。

visited 要在入队时标记，而不是出队时标记，才能避免同层重复入队。

每层先固定 size，处理结束后再增加 step，否则距离会与出队次数混淆。

生成某一位的两个邻居后要恢复原字符，才能继续正确修改下一位。

易错点总结

[!yellow]

起点必须先检查是否死亡，后续邻居也要过滤死亡状态；仅仅把它们加入访问集合并不能自动保证起点合法。

层内循环不能随着新状态入队而扩大范围，必须使用预先保存的 size；step++ 也只能放在整层结束之后。

两个转动方向都应基于原数字，且要处理 0 向下到 9、9 向上到 0 的环形边界。处理下一拨轮前必须恢复上一位。

只在生成邻居时判断目标会漏掉零步答案；当前实现把起点也入队，并统一在出队时判断。

相似题目

题目	难度	关联与区别
773. 滑动谜题	困难	同样把完整局面编码为状态，按一次合法操作生成邻居，再用BFS求最少步数。
127. 单词接龙	困难	同样搜索单位边状态图，原题邻居是合法字典词，本题邻居由转动某一位生成。
1091. 二进制矩阵中的最短路径	中等	把合法状态及一次操作建成无权图进行 BFS；本题按转动一位数字扩展状态，该题按可通行的相邻单元扩展路径。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/50393373

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！