LeetCode 752. 打开转盘锁

字数 2403 2025-10-26 09:00:43

LeetCode 752. 打开转盘锁

题目描述
你有一个带有四个圆形拨轮的转盘锁，每个拨轮有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，或者把 '0' 变为 '9'。每次旋转都只能将一个拨轮旋转一个数字（即递增或递减一位）。

锁的初始状态是 '0000'，代表四个拨轮都在 '0' 的位置。

给你一个字符串列表 deadends，代表一组死亡数字。一旦拨轮的数字和列表里的任何一个元素相同，这个锁就会被永久锁定，无法再被旋转。

同时，给你一个目标字符串 target。你需要计算出从初始状态 '0000' 开始，至少需要旋转多少次拨轮，才能得到目标状态。如果无论如何都无法达到目标，则返回 -1。

解题过程

这个问题可以被看作是在一个图结构中进行最短路径搜索。我们可以将每个锁的状态（如"0000"）视为图中的一个节点。如果两个状态之间可以通过旋转一个拨轮一次（递增或递减）来相互转换，那么这两个节点之间就存在一条边。我们的目标是找到从节点"0000"到节点target的最短路径长度（即旋转次数）。由于每次旋转的代价相同（1次），我们可以使用广度优先搜索（BFS） 算法，因为BFS天然地按层（按距离）遍历节点，第一次遇到目标节点时，所经历的层数就是最短路径。

步骤详解

特殊情况处理
- 首先检查初始状态 "0000" 是否在死亡数字列表中。如果在，说明一开始锁就被卡住了，直接返回 -1。
- 如果目标状态 target 就是 "0000"，那么不需要任何旋转，直接返回 0。
初始化BFS所需的数据结构
- 队列 (queue)：用于存储待访问的节点。我们首先将初始状态 "0000" 加入队列。
- 已访问集合 (visited)：用于记录已经访问过的节点，避免重复访问和死循环。我们也将初始状态 "0000" 加入已访问集合。同时，为了简化逻辑，我们可以直接将 deadends 列表中的所有状态也加入已访问集合，因为它们是不可达的节点。
- 步数计数器 (step)：初始化为 0，代表从起点开始的旋转次数。
开始BFS循环
- 只要队列不为空，我们就继续循环。每一轮循环对应着探索“当前步数”下所有可能到达的状态。
- 在每一轮循环开始时，我们记录当前队列的大小 size。这个 size 代表了在当前步数 step 下，有多少个状态等待我们去探索它们的邻居。
- 然后，我们依次从队列中取出 size 个节点进行处理。
  - 对于当前取出的节点 current：
    - 判断是否到达目标：如果 current 等于 target，说明我们已经找到了最短路径，立即返回当前的步数 step。
    - 生成邻居节点：如果还没到达目标，我们需要生成 current 的所有邻居节点。对于一个四位数锁，每个位置可以向上旋转（数字+1）或向下旋转（数字-1），因此每个节点有 4个位置 × 2个方向 = 8个邻居。
      - 向上旋转：例如，对于某一位字符 c（如 '5'），向上旋转的结果是 (c - '0' + 1) % 10，再将结果转换为字符。这样，'9' + 1 会变成 (9+1)%10 = 0，符合要求。
      - 向下旋转：向下旋转的结果是 (c - '0' - 1 + 10) % 10，再加10是为了处理负数，取模后得到正确结果。这样，'0' - 1 会变成 (0-1+10)%10 = 9，符合要求。
    - 对于这8个新生成的邻居状态 neighbor：
      - 检查有效性：检查 neighbor 是否存在于 visited 集合中。如果不存在，说明它是一个既未访问过也不是死亡数字的有效新状态。
      - 标记和入队：将这个有效的 neighbor 加入 visited 集合（标记为已发现），同时加入队列，等待下一轮的探索。
- 在处理完当前层的所有 size 个节点后，我们将步数 step 加 1，表示我们即将探索下一层（即旋转次数多一次的状态）。
循环结束后的处理
- 如果BFS循环结束（队列为空）我们还没有返回结果，意味着我们从 "0000" 出发，遍历了所有可能到达的状态，但始终没有遇到 target。这说明 target 被死亡数字包围或是初始状态就无法到达，因此返回 -1。

举例说明
以 deadends = ["0201","0101","0102","1212","2002"], target = "0202" 为例。

初始：step=0, queue = ["0000"], visited = {"0000", "0201", "0101", "0102", "1212", "2002"}
第1步 (step=0)：处理 "0000"。它的邻居有 "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"。过滤掉在 visited 中的，假设 "0100" 等是有效的，加入队列。此时 step 变为 1。
第2步 (step=1)：处理上一层的8个邻居。从这些状态继续扩展，我们会逐步接近 "0202"。最终，我们会发现一条路径，比如 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"（这只是一个可能路径，BFS会找到最短的）。当队列取出的节点是 "0202" 时，返回当前的步数（例如6）。

通过这种逐层扩散的BFS，我们保证第一次遇到 target 时，所用的步数就是最短的旋转次数。

LeetCode 752. 打开转盘锁题目描述你有一个带有四个圆形拨轮的转盘锁，每个拨轮有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，或者把 '0' 变为 '9'。每次旋转都只能将一个拨轮旋转一个数字（即递增或递减一位）。锁的初始状态是 '0000'，代表四个拨轮都在 '0' 的位置。给你一个字符串列表 deadends ，代表一组死亡数字。一旦拨轮的数字和列表里的任何一个元素相同，这个锁就会被永久锁定，无法再被旋转。同时，给你一个目标字符串 target 。你需要计算出从初始状态 '0000' 开始，至少需要旋转多少次拨轮，才能得到目标状态。如果无论如何都无法达到目标，则返回 -1。解题过程这个问题可以被看作是在一个图结构中进行最短路径搜索。我们可以将每个锁的状态（如"0000"）视为图中的一个节点。如果两个状态之间可以通过旋转一个拨轮一次（递增或递减）来相互转换，那么这两个节点之间就存在一条边。我们的目标是找到从节点"0000"到节点 target 的最短路径长度（即旋转次数）。由于每次旋转的代价相同（1次），我们可以使用广度优先搜索（BFS）算法，因为BFS天然地按层（按距离）遍历节点，第一次遇到目标节点时，所经历的层数就是最短路径。步骤详解特殊情况处理首先检查初始状态 "0000" 是否在死亡数字列表中。如果在，说明一开始锁就被卡住了，直接返回 -1。如果目标状态 target 就是 "0000"，那么不需要任何旋转，直接返回 0。初始化BFS所需的数据结构队列 ( queue ) ：用于存储待访问的节点。我们首先将初始状态 "0000" 加入队列。已访问集合 ( visited ) ：用于记录已经访问过的节点，避免重复访问和死循环。我们也将初始状态 "0000" 加入已访问集合。同时，为了简化逻辑，我们可以直接将 deadends 列表中的所有状态也加入已访问集合，因为它们是不可达的节点。步数计数器 ( step ) ：初始化为 0，代表从起点开始的旋转次数。开始BFS循环只要队列不为空，我们就继续循环。每一轮循环对应着探索“当前步数”下所有可能到达的状态。在每一轮循环开始时，我们记录当前队列的大小 size 。这个 size 代表了在当前步数 step 下，有多少个状态等待我们去探索它们的邻居。然后，我们依次从队列中取出 size 个节点进行处理。对于当前取出的节点 current ：判断是否到达目标：如果 current 等于 target ，说明我们已经找到了最短路径，立即返回当前的步数 step 。生成邻居节点：如果还没到达目标，我们需要生成 current 的所有邻居节点。对于一个四位数锁，每个位置可以向上旋转（数字+1）或向下旋转（数字-1），因此每个节点有 4个位置 × 2个方向 = 8个邻居。向上旋转：例如，对于某一位字符 c （如 '5'），向上旋转的结果是 (c - '0' + 1) % 10 ，再将结果转换为字符。这样，'9' + 1 会变成 (9+1)%10 = 0，符合要求。向下旋转：向下旋转的结果是 (c - '0' - 1 + 10) % 10 ，再加10是为了处理负数，取模后得到正确结果。这样，'0' - 1 会变成 (0-1+10)%10 = 9，符合要求。对于这8个新生成的邻居状态 neighbor ：检查有效性：检查 neighbor 是否存在于 visited 集合中。如果不存在，说明它是一个既未访问过也不是死亡数字的有效新状态。标记和入队：将这个有效的 neighbor 加入 visited 集合（标记为已发现），同时加入队列，等待下一轮的探索。在处理完当前层的所有 size 个节点后，我们将步数 step 加 1，表示我们即将探索下一层（即旋转次数多一次的状态）。循环结束后的处理如果BFS循环结束（队列为空）我们还没有返回结果，意味着我们从 "0000" 出发，遍历了所有可能到达的状态，但始终没有遇到 target 。这说明 target 被死亡数字包围或是初始状态就无法到达，因此返回 -1。举例说明以 deadends = ["0201","0101","0102","1212","2002"] , target = "0202" 为例。初始： step=0 , queue = ["0000"] , visited = {"0000", "0201", "0101", "0102", "1212", "2002"} 第1步 (step=0) ：处理 "0000"。它的邻居有 "1000", "9000", "0100", "0900", "0010", "0090", "0001", "0009"。过滤掉在 visited 中的，假设 "0100" 等是有效的，加入队列。此时 step 变为 1。第2步 (step=1) ：处理上一层的8个邻居。从这些状态继续扩展，我们会逐步接近 "0202"。最终，我们会发现一条路径，比如 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"（这只是一个可能路径，BFS会找到最短的）。当队列取出的节点是 "0202" 时，返回当前的步数（例如6）。通过这种逐层扩散的BFS，我们保证第一次遇到 target 时，所用的步数就是最短的旋转次数。