LeetCode 题解工作台
打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0' ， '0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
直接用朴素 BFS。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 输出：6 解释： 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的， 因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009" 输出：1 解释：把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" 输出：-1 解释：无法旋转到目标数字且不被锁定。
提示：
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4target不在deadends之中target和deadends[i]仅由若干位数字组成
解题思路
方法一：朴素 BFS
直接用朴素 BFS。
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
def next(s):
res = []
s = list(s)
for i in range(4):
c = s[i]
s[i] = '9' if c == '0' else str(int(c) - 1)
res.append(''.join(s))
s[i] = '0' if c == '9' else str(int(c) + 1)
res.append(''.join(s))
s[i] = c
return res
if target == '0000':
return 0
s = set(deadends)
if '0000' in s:
return -1
q = deque([('0000')])
s.add('0000')
ans = 0
while q:
ans += 1
for _ in range(len(q)):
p = q.popleft()
for t in next(p):
if t == target:
return ans
if t not in s:
q.append(t)
s.add(t)
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(4(d + 10^4)) because each of the 4 wheels can change per node, with at most 10^4 possible states, and d deadends. Space complexity is O(4(d + 10^4)) for the BFS queue and visited/deadend hash sets. |
| 空间 | O(4(d + 10^4)) |
面试官常问的追问
外企场景- question_mark
Look for a BFS pattern and early pruning using deadend hash set.
- question_mark
Expect recognition that each state has up to 8 neighbors due to wheel increments and decrements.
- question_mark
Consider wraparound behavior and edge cases like starting or ending on a deadend.
常见陷阱
外企场景- error
Failing to account for wraparound when incrementing '9' or decrementing '0'.
- error
Revisiting states without checking visited hash set, causing infinite loops.
- error
Miscounting moves by including deadend transitions or skipping BFS levels.
进阶变体
外企场景- arrow_right_alt
Solve using bidirectional BFS from both start and target for faster convergence.
- arrow_right_alt
Consider a lock with N wheels instead of 4, adjusting BFS accordingly.
- arrow_right_alt
Introduce weighted moves, where some wheel turns cost more, and find minimum total cost.