打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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 <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 仅由若干位数字组成
示例代码: 【广度优先搜索BFS】
from collections import deque
class Solution(object):
def openLock(self, deadends, target):
if target == "0000":
return 0
dead = set(deadends)
if "0000" in dead:
return -1
def num_pre(x):
return "9" if x == "0" else str(int(x) - 1)
def num_post(x):
return "0" if x == "9" else str(int(x) + 1)
# 枚举 status 通过一次旋转得到的数字
def generator_num(status):
s = list(status)
for i in range(4):
num = s[i]
s[i] = num_pre(num)
yield ''.join(s)
s[i] = num_post(num)
yield ''.join(s)
s[i] = num
quene = deque([("0000", 0)])
tmp = {"0000"}
while quene:
status, step = quene.popleft()
for next_status in generator_num(status):
if next_status not in tmp and next_status not in dead:
if next_status == target:
return step + 1
quene.append((next_status, step + 1))
tmp.add(next_status)
return -1
deadends = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
obj = Solution()
ans = obj.openLock(deadends, target)
print(ans)
思路解析:
使用BFS,找出从初始数字 0000 到解锁数字 target 的最小旋转次数。
具体地,一开始将 (0000, 0)加入队列,并使用该队列进行广度优先搜索。在搜索的过程中,设当前搜索到的数字为 status,旋转的次数为step,我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为 next_status,如果其没有被搜索过,我们就将 (next_status,step+1) 加入队列。如果搜索到了target,我们就返回其对应的旋转次数。
为了避免搜索到死亡数字,使用哈希表存储deadends 中的所有元素,这样在搜索的过程中,我们可以均摊 O(1)地判断一个数字是否为死亡数字。同时,还需要一个哈希表存储所有搜索到的状态,避免重复搜索。
如果搜索完成后,仍没有搜索到 target,说明我们无法解锁,返回 -1。
时间复杂度:
示例代码2:
from collections import deque
class Solution(object):
def openLock(self, deadends, target):
# 如果target是'0000'则不需要拨动 返回0
if target == "0000":
return 0
dead = set(deadends)
if "0000" in dead:
return -1
def num_up(x, i):
lst = list(x)
if lst[i] == "9":
lst[i] = "0"
else:
lst[i] = str(int(lst[i]) + 1)
return "".join(lst)
def num_down(x, i):
lst = list(x)
if lst[i] == "0":
lst[i] = "9"
else:
lst[i] = str(int(lst[i]) - 1)
return "".join(lst)
step = 0 # 拨动次数 初始时没拨所以次数为0
queue = deque()
visited = set() # 存放已经比较过的字符组合、死亡数字组合 避免死循环
visited.update(deadends) # 初始化为死亡数字组合
queue.append("0000")
while queue:
length = len(queue) # 按层处理队列中的字符串
for i in range(length):
cur = queue.popleft() # 当前处理的节点
if cur in visited: # 当前节点已经处理过或属于死亡数字组合 所以跳过
continue
else:
visited.add(cur) # 首次比较 加入已经处理的集合
# 判断是否满足终止条件
if cur == target:
return step
# 不满足终止条件将所有相邻的节点加入队列
for j in range(4): # cur的每位数都可以上拨或下拨 这些都是cur的相邻节点
up = num_up(cur, j)
# 需要判断上拨、下拨后的组合是否合法(在不在visited里) 不合法就跳过
if up not in visited:
queue.append(up)
down = num_down(cur, j)
if down not in visited:
queue.append(down)
# 每循环一遍是一次拨动 次数要+1
step += 1
# 所有可能都穷举后无法达到target说明不能解锁 返回-1
return -1
deadends = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
obj = Solution()
ans = obj.openLock(deadends, target)
print(ans)
思路解析:
密码锁可以看作是一层一层的,因为在穷举可能的密码组合时,每一位每次有2种(上拨、下拨)情况,依据每种情况又可以再次延伸……这种特性可以采用BFS思想求解,想象一下按层处理每种密码组合:
将起点加入队列q,只要q不为空,循环处理当前层的节点(循环条件是进入循环时q的长度),若当前节点cur是终点(target)则结束循环返回处理次数(层数)step,否则将cur的邻接节点(下一层的节点)加入q,一轮循环处理结束step++。当队列q为空(全部节点都处理完后)说明没有满足结束条件的节点,即不存在解,返回-1。
相关文章
- AndroidStudio快捷键——打开最近编辑文件列表视图——(一)
- 每次打开office 2013都提示配置进度,必须得等他下完然后重启,重启完了在打开,还是提示配置进度,怎么解决
- ES6判断当前页面是否微信浏览器中打开
- linux设置打开文件句柄数
- 【快应用】快应用如何打开手机中的html文件
- iOS10 打开APP设置界面和WIFI界面
- Win7下打开计算机管理时出现错误的解决办法
- open, creat - 用来 打开和创建 一个 文件或设备
- js判断移动端是否安装某软软件,安装直接打开相应的链接,否则跳转到下载商店方法
- 中秋节之Python绘制许愿树和月饼(打开程序员世界的大门)
- 【原】使用SQLite打开本地*.db文件
- CAD图纸文件很小为什么打开或操作很慢?
- 还得靠运营商 华为拟借力AT&T打开美国市场