LeetCode 752. 打开转盘锁

字数 2106 2025-10-26 19:15:23

LeetCode 752. 打开转盘锁

题目描述

想象一个带有四个圆形转盘的密码锁。每个转盘有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。转盘可以自由旋转：每个转盘可以向前旋转一位（例如，从 '0' 转到 '1'）或向后旋转一位（例如，从 '0' 转到 '9'）。密码锁的初始状态是 "0000"，一个由四个数字组成的字符串。

你被给了一个字符串列表 deadends，这些是“死亡数字”，意味着如果锁的状态变成了列表中的任何一个，锁将永久卡死，无法再进行任何旋转。同时，你还有一个目标字符串 target。你的任务是计算出将锁从初始状态 "0000" 旋转到目标状态 target 所需的最少步数。如果无法实现，则返回 -1。

一次旋转操作只能改变一个转盘的一个数字（向前或向后旋转一位）。

解题过程

我们将使用广度优先搜索（BFS）算法来解决这个问题。BFS非常适合寻找无权图中的最短路径，而这个问题恰好可以建模为一个图：

节点：每一个可能的四位数锁状态（例如，"0000", "0001", ..., "9999"），总共10000个节点。
边：如果两个状态可以通过旋转一个转盘的一位来相互转换，那么它们之间就存在一条边。每个节点有8个邻居（4个转盘，每个转盘可以向前或向后转）。

BFS会从起点 "0000" 开始，一层一层地向外探索。第一层是距离起点为1步的所有状态，第二层是距离起点为2步的所有状态，以此类推。当我们第一次遇到目标状态 target 时，当前的层数（即步数）就是最短路径。

步骤详解

初始检查与特殊情况处理
- 首先检查起点 "0000" 是否在死亡数字列表 deadends 中。如果在，说明一开始锁就卡死了，直接返回 -1。
- 检查目标 target 是否是起点 "0000"。如果是，则不需要旋转，直接返回 0。
初始化数据结构
- 队列 (Queue)：用于BFS遍历，遵循先进先出的原则。我们将待探索的节点（锁状态）放入队列。初始时，将起点 "0000" 加入队列。
- 已访问集合 (Visited Set)：用于记录已经访问过的节点，避免重复访问和死循环。因为死亡数字永远不能访问，我们可以在一开始就把所有 deadends 中的状态也加入这个集合。初始时，将 deadends 中的所有字符串和 "0000" 加入已访问集合。
开始BFS循环
- 初始化一个变量 steps 来记录当前的旋转步数，初始为 0（因为起点尚未开始旋转）。
- 只要队列不为空，就继续循环。每一轮循环处理当前步数下的所有可能状态。
  - 将 steps 加1，表示我们将要探索从起点出发，经过 steps 步能到达的状态。
  - 记录当前队列的大小 size。这个 size 代表了在第 steps-1 步时，我们有多少个状态。我们将依次处理这些状态，并探索它们的所有邻居。
  - 进行一个内层循环，循环 size 次：
    a. 从队列中取出一个当前状态，比如 "1234"。
    b. 生成这个状态的所有邻居（下一个可能的状态）。对于一个四位数，每个数字有两种变化（加1或减1），所以共有 4 * 2 = 8 个邻居。
    - 对于每一位（从第0位到第3位）：
    - 向前旋转：将该位数字加1。如果原来是 '9'，则变为 '0'。
    - 向后旋转：将该位数字减1。如果原来是 '0'，则变为 '9'。
    - 例如，对于状态 "0000"，它的邻居包括 "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"。
    c. 检查每一个新生成的邻居状态：
    - 如果这个邻居状态等于目标状态 target，恭喜你！我们已经找到了最短路径，立即返回当前的步数 steps。
    - 如果这个邻居状态不在已访问集合中（即既不是死亡数字，也从未被访问过），那么：
    - 将它加入已访问集合，标记为已访问。
    - 将它加入队列，等待在下一轮（steps+1 步）中进行探索。
循环结束后的处理
- 如果BFS循环结束（队列为空）我们还没有返回结果，这意味着我们从起点 "0000" 出发，遍历了所有可能到达的状态，但始终没有找到目标状态 target。此时，返回 -1，表示无法打开锁。

为什么BFS能保证找到的是最短路径？
因为BFS是按“层”探索的。它总是先访问所有距离起点为1步的节点，再访问距离为2步的节点。因此，当它第一次遇到目标节点时，所经过的步数必然是最短的。

总结
这个算法的核心是将锁的状态变化抽象成图的遍历问题，利用BFS一层层扩展的特性来寻找最短旋转次数。关键点在于使用队列进行BFS，并使用集合来避免重复访问和处理死亡数字。

LeetCode 752. 打开转盘锁题目描述想象一个带有四个圆形转盘的密码锁。每个转盘有10个数字： '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' 。转盘可以自由旋转：每个转盘可以向前旋转一位（例如，从 '0' 转到 '1' ）或向后旋转一位（例如，从 '0' 转到 '9' ）。密码锁的初始状态是 "0000" ，一个由四个数字组成的字符串。你被给了一个字符串列表 deadends ，这些是“死亡数字”，意味着如果锁的状态变成了列表中的任何一个，锁将永久卡死，无法再进行任何旋转。同时，你还有一个目标字符串 target 。你的任务是计算出将锁从初始状态 "0000" 旋转到目标状态 target 所需的最少步数。如果无法实现，则返回 -1 。一次旋转操作只能改变一个转盘的一个数字（向前或向后旋转一位）。解题过程我们将使用广度优先搜索（BFS）算法来解决这个问题。BFS非常适合寻找无权图中的最短路径，而这个问题恰好可以建模为一个图：节点：每一个可能的四位数锁状态（例如，"0000", "0001", ..., "9999"），总共10000个节点。边：如果两个状态可以通过旋转一个转盘的一位来相互转换，那么它们之间就存在一条边。每个节点有8个邻居（4个转盘，每个转盘可以向前或向后转）。 BFS会从起点 "0000" 开始，一层一层地向外探索。第一层是距离起点为1步的所有状态，第二层是距离起点为2步的所有状态，以此类推。当我们第一次遇到目标状态 target 时，当前的层数（即步数）就是最短路径。步骤详解初始检查与特殊情况处理首先检查起点 "0000" 是否在死亡数字列表 deadends 中。如果在，说明一开始锁就卡死了，直接返回 -1 。检查目标 target 是否是起点 "0000" 。如果是，则不需要旋转，直接返回 0 。初始化数据结构队列 (Queue) ：用于BFS遍历，遵循先进先出的原则。我们将待探索的节点（锁状态）放入队列。初始时，将起点 "0000" 加入队列。已访问集合 (Visited Set) ：用于记录已经访问过的节点，避免重复访问和死循环。因为死亡数字永远不能访问，我们可以在一开始就把所有 deadends 中的状态也加入这个集合。初始时，将 deadends 中的所有字符串和 "0000" 加入已访问集合。开始BFS循环初始化一个变量 steps 来记录当前的旋转步数，初始为 0 （因为起点尚未开始旋转）。只要队列不为空，就继续循环。每一轮循环处理当前步数下的所有可能状态。将 steps 加1，表示我们将要探索从起点出发，经过 steps 步能到达的状态。记录当前队列的大小 size 。这个 size 代表了在第 steps-1 步时，我们有多少个状态。我们将依次处理这些状态，并探索它们的所有邻居。进行一个内层循环，循环 size 次： a. 从队列中取出一个当前状态，比如 "1234" 。 b. 生成这个状态的所有邻居（下一个可能的状态）。对于一个四位数，每个数字有两种变化（加1或减1），所以共有 4 * 2 = 8 个邻居。 - 对于每一位（从第0位到第3位）： - 向前旋转：将该位数字加1。如果原来是 '9' ，则变为 '0' 。 - 向后旋转：将该位数字减1。如果原来是 '0' ，则变为 '9' 。 - 例如，对于状态 "0000" ，它的邻居包括 "1000" , "9000" , "0100" , "0900" , "0010" , "0090" , "0001" , "0009" 。 c. 检查每一个新生成的邻居状态： - 如果这个邻居状态等于目标状态 target ，恭喜你！我们已经找到了最短路径，立即返回当前的步数 steps 。 - 如果这个邻居状态不在已访问集合中（即既不是死亡数字，也从未被访问过），那么： - 将它加入已访问集合，标记为已访问。 - 将它加入队列，等待在下一轮（ steps+1 步）中进行探索。循环结束后的处理如果BFS循环结束（队列为空）我们还没有返回结果，这意味着我们从起点 "0000" 出发，遍历了所有可能到达的状态，但始终没有找到目标状态 target 。此时，返回 -1 ，表示无法打开锁。为什么BFS能保证找到的是最短路径？因为BFS是按“层”探索的。它总是先访问所有距离起点为1步的节点，再访问距离为2步的节点。因此，当它第一次遇到目标节点时，所经过的步数必然是最短的。总结这个算法的核心是将锁的状态变化抽象成图的遍历问题，利用BFS一层层扩展的特性来寻找最短旋转次数。关键点在于使用队列进行BFS，并使用集合来避免重复访问和处理死亡数字。