Python版-LeetCode 学习:752. 打开转盘锁
程序员文章站
2022-04-27 16:54:56
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转:例如把 '9' 变为'0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。字符串 target 代表可以解锁的......
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以*旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/open-the-lock
方法1:双向BFS算法
传统的 BFS 框架就是从起点开始向四周扩散,遇到终点时停止;而双向 BFS 则是从起点和终点同时开始扩散,当两边有交集的时候停止。如果“终点”(目标值)在二叉树的最底部,按照传统 BFS 算法的策略,会把整棵树的节点都搜索一遍,最后找到 target
;而双向 BFS 其实只遍历了半棵树就出现了交集,也就是找到了最短距离。直观地看,双向 BFS 是要比传统 BFS 高效的多。但双向BFS也有局限性,就是你需要知道“终点”(目标值)在哪。你一开始根本就不知道终点在哪里,也就无法使用双向 BFS;但是第二个密码锁的问题,是可以使用双向 BFS 算法来提高效率。
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
def onePlus(s:str,j: int)-> str:
# 将s[i]向上拨动一次
strList=list(s)
if strList[j]=='9':
strList[j]='0'
else:
strList[j]=str(int(strList[j])+1)
return ''.join(strList)
def oneMinus(s,j):
# 将s[i]向下拨动一次
strList=list(s)
if strList[j]=='0':
strList[j]='9'
else:
strList[j]=str(int(strList[j])-1)
return ''.join(strList)
# 利用set提高查询速度
deadendSet=set(deadends)
visited=set()
queue=set()
# 从0000开始
queue.add('0000')
visited.add('0000')
# 从目标值开始
queue2=set()
queue2.add(target)
step=0
while queue and queue2 :
tmp=set()
if (len(queue) > len(queue2)):
#按照 BFS 的逻辑,队列(集合)中的元素越多,扩散之后新的队列(集合)中的元素就越多;
# 在双向 BFS 算法中,如果我们每次都选择一个较小的集合进行扩散,那么占用的空间增长速度就会慢一些,效率就会高一些。所以这里进行一次交换
queue,queue2 = queue2,queue
for cur in queue:
if cur in deadendSet:
continue
if cur in queue2:
return step
# 记录已经使用过的组合
visited.add(cur)
# 上下拨动的可能值放入循环队列
for j in range(4):
up=onePlus(cur,j)
if (up not in visited):
tmp.add(up)
down=oneMinus(cur,j)
if down not in visited:
tmp.add(down)
# 步数加一
step+=1
# temp 相当于 queue,交换queue,queue2,下一轮 while 就是扩散 q2
queue=queue2
queue2=tmp
return -1
方法2:
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
# 定义一个距离函数,计算一个code直接拨需要多少下,比如0004就是4下,0009就是1下。
def dist(code):
return sum([min(int(c), 10-int(c)) for c in code])
if "0000" in deadends or target in deadends :
return -1
# 由target反推能够到达target的所有前一个节点,放在 new_codes 里返回。
new_codes = []
for i in range(4):
pre, x, sur = target[:i], int(target[i]), target[i+1:]
new_codes.append(pre + str((x+1)%10) + sur)
new_codes.append(pre + str((x-1)%10) + sur)
# 利用集合(set)是可以做减法,得出不在deadends里面的new_codes,放在 moves 里。
# set的减法:例如{'0001','0003','0015'} - {'0003','0007'} = {'0001', '0015'}
moves = set(new_codes) - set(deadends)
# 如果moves为空,那就说明没有路径可以到达target,那就返回 -1
if not moves:
return -1
# 计算直接播到目标值需要多少次
result = dist(target) # 例如 result = dist('0088') ,那么 result就等于4
# 遍历所有排除掉deadends的选项,计算这里面的值
# 判断是否有大于直接到达目标值的选项
for move in moves:
if dist(move) < result: # 如果存在任一个到达target的前一节点,则直接到达target就是可能的
return result
return result + 2 # 如果所有target的前一节点的到达距离都比直接到达target大,则就返回 result + 2
方法3:该方法同方法2思路类似,但要比方法2空间复杂度更小
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
def distance(string):
return sum(min(int(num), 10 - int(num)) for num in string)
if '0000' in deadends or target in deadends:
return -1
moves = {str(i): (str((i - 1) % 10), str((i + 1) % 10)) for i in range(10)}
adjacent = set()
for i in range(len(target)):
start = target[:i]
end = target[i + 1:]
for j in moves[target[i]]:
adjacent.add(start + j + end)
possibleMoves = adjacent - set(deadends)
if not possibleMoves:
return -1
return min(distance(move) for move in possibleMoves) + 1
本文地址:https://blog.csdn.net/guyu1003/article/details/107296073