【leetcoded-Python】-BFS-752. Open the Lock

概述题目链接https://leetcode.com/problems/open-the-lock题目描述给你一个带有4个圆形拨轮的转盘锁。每个拨轮有10个数字：'0','1','2','3','4','5','6','7','8','9'。每个拨轮可以自由旋转：例如把'9& 题目链接

https://leetcode.com/problems/open-the-lock

题目描述

给你一个带有4个圆形拨轮的转盘锁。每个拨轮有10个数字：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例

输入：deadends = ["0201","0101","0102","1212","2002"],target = "0202"

输出：6

可能的移动序列为："0000"->"1000"->"1100"->"1200"->"1201"->"1202"->"0202"

需要注意的是"0000"->"0001"->"0002"->"0102"->"0202"这样的序列是不能被解锁的，因为拨动到"0102"时锁会被锁定。

解题思路

由于有4把锁，即一共有4个位置，每个位置可以向上转也可以向下转，因此每转动一次有八种可能。因此这个问题可以抽象成一个图，每个节点有8个相邻节点，求"0000"到目标节点target的最短距离。因此这道题可以用BFS来做。

但是需要在BFS模板的基础上增加对deadends的处理，如果有节点在deadends内，就需要跳过这个节点。因为这个节点是不能出现在路径中的。同时在这道题中要维护好visited集合，避免走回头路。

在代码实现时， 抽象出函数moveUp(s,i)和moveDown(s,i)，分别表示将s[i]向上拨动一次和向下拨动一次的结果。

注意在Python中，字符串是不可变类型，即无法直接修改字符串的某一位字符。因此我们采取先将字符串转为List，然后再用join将List中的元素拼成字符串。

代码实现

class Solution:    def openLock(self, deadends: List[str], target: str) -> int:        #s[i]向上拨动后得到的新字符串        def moveUp(s,i):            s = List(s)#字符串是不可变类型，无法直接修改字符串中的某个字符，因此我们先转为列表修改某个字符后，再转为字符串            if s[i] == '0': #0往上拨就是9                s[i] = '9'             else:                s[i] = str(int(s[i])-1)            return ''.join(s)        #s[i]向下拨动后得到的新字符串        def moveDown(s,i):            s = List(s)            if s[i] == '9': #9往下拨就是0                s[i] = '0'            else:                s[i] = str(int(s[i])+1)            return ''.join(s)                queue = ['0000'] #BFS所用队列，先将起始点加入        visited = set('0000') #存储已经访问过的节点        step = 0        while queue:#队列不为空的情况下进行循环            #先把这一层遍历完，因此找queue的大小            n = len(queue)            for num in range(n):                cur = queue.pop(0) #d出队首元素并判断                if (cur == target):                    return step                if (cur in deadends): #判断当前节点是否在deadends中                    continue                #将相邻的8个”节点”加入队列                for i in range(4):                    tmp_up = moveUp(cur,i)                    if tmp_up not in visited: #一定要注意这里要有判断                        #加入队列                        queue.append(tmp_up)                        #改变访问状态                        visited.add(tmp_up)                    tmp_down = moveDown(cur,i)                    if tmp_down not in visited:                        #加入队列                        queue.append(tmp_down)                        # 改变访问状态                        visited.add(tmp_down)            step += 1 #这一层遍历完了之后增加步数            return -1 #等queue为空时遍历结束，如果没有找到target就要返回-1                                        @H_403_38@

参考

https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/bfs-suan-fa/bfs-kuang-jia

https://www.jb51.net/article/150063.htm

 

 

 

总结

以上是内存溢出为你收集整理的【leetcoded-Python】-BFS-752. Open the Lock全部内容，希望文章能够帮你解决【leetcoded-Python】-BFS-752. Open the Lock所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1188319.html