欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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