LeetCode 752. 打开转盘锁 题目描述 你有一个带有四个圆形拨轮的转盘锁，每个拨轮有 10 个数字： '0' 到 '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0' ，或把 '0' 变为 '9' 。每次旋转只能将一个拨轮旋转一个位置。 锁的初始数字为 "0000" ，一个代表四个拨轮数字的字符串。 列表 deadends 包含了一组死亡数字，表示一旦拨轮数字和列表里的任何一个元素相同，锁将会被永久锁定，无法再被旋转。 给你一个目标数字 target ，请计算从初始状态 "0000" 旋转到 target 需要的最少旋转次数。如果无法实现，返回 -1 。 解题过程 1. 问题分析 这个问题可以看作是在一个图中寻找最短路径： 节点 ：每个四位数密码（如 "0000" 、 "0001" 等）是一个状态。 边 ：如果两个密码之间可以通过旋转一个拨轮一位数字来互相转换（例如 "0000" 可以转到 "1000" 、 "9000" 、 "0100" 等 8 个邻居），则它们之间有一条边。 目标 ：从起始节点 "0000" 出发，找到到目标节点 target 的最短路径（BFS 天然适合）。 约束 ： deadends 中的节点是障碍，不可访问。 2. 基础思路：BFS 广度优先搜索（BFS）会一层层扩展节点，第一次遇到 target 时的路径长度就是最小旋转次数。 步骤： 如果 "0000" 在 deadends 中，直接返回 -1 。 队列中放入 ("0000", 0) （节点和当前步数）。 使用 visited 集合记录已访问节点（避免重复访问和死循环）。 对于队列中的每个节点，生成它的 8 个邻居（每个拨轮向上或向下转一次）。 如果邻居不在 visited 且不在 deadends 中，则加入队列。 遇到 target 则返回步数。 队列为空仍未找到则返回 -1 。 3. 邻居生成方法 对于密码 "abcd" ，第 i 位（0~3）可以： 向上转： (digit + 1) % 10 向下转： (digit + 9) % 10 （等同于 (digit - 1 + 10) % 10 ） 例如对 "0000" 第 0 位向上转： "1000" ；向下转： "9000" 。 4. 优化：双向 BFS 从起点和终点同时开始 BFS，每次扩展较小的一边。如果两边相遇（有公共节点），则路径长度为两边步数之和。 优势：减少搜索空间，尤其当目标较远时。 实现： 使用两个集合 q1 和 q2 代替队列，记录当前层的所有节点。 每次选择较小的集合进行扩展。 扩展时检查是否在另一个集合中出现。 5. 代码步骤（双向 BFS） 若 "0000" 在 deadends 或 target 在 deadends ，返回 -1 。 若 "0000" == target ，返回 0 。 初始化两个集合： q1 = {"0000"} , q2 = {target} ，visited 包含 deadends。 步数 step = 0 。 当 q1 和 q2 均非空： 总是扩展较小的集合（交换保证 q1 是较小的）。 创建临时集合 temp 存放下一层节点。 对 q1 中每个节点，生成 8 个邻居，若不在 visited 中则加入 temp。 如果 temp 中有节点在 q2 中，返回 step + 1 （因为相遇）。 将 temp 加入 visited（标记已访问）。 q1 = temp ， step++ 。 若循环结束未相遇，返回 -1 。 6. 复杂度分析 时间复杂度：O(10^4) = O(10000)（最多 10000 个状态）。 空间复杂度：O(10000)（存储 visited 和队列）。 双向 BFS 在实践中比单向 BFS 减少约一半的搜索节点。