Python版-LeetCode 学习：752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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