1. 首页
  2. IT资讯

Leetcode 打开转盘锁

 

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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 解释: 无法旋转到目标数字且不被锁定。 

示例 4:

 输入: deadends = ["0000"], target = "8888" 输出:-1 

 

提示:

  1. 死亡列表 deadends 的长度范围为 [1, 500]
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
 from queue import Queue  class Solution:     def openLock(self, deadends: List[str], target: str) -> int:         deadends = set(deadends) # in 操作在set中时间复杂度为O(1)         if '0000' in deadends:             return -1                  # -------------------------------BFS 开始----------------------------------         # 初始化根节点         q = Queue()         q.put(('0000', 0)) # (当前节点值,转动步数)                  # 开始循环队列         while not q.empty():                          # 取出一个节点             node, step = q.get()                          # 放入周围节点             for i in range(4):                 for add in (1, -1):                     cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:]                     if cur == target:                         return step + 1                     if not cur in deadends:                         q.put((cur, step + 1))                         deadends.add(cur) # 避免重复搜索         # -------------------------------------------------------------------------         return -1  作者:QQqun902025048 链接:https://leetcode-cn.com/problems/two-sum/solution/python-bfs-qing-xi-ti-jie-by-knifezhu/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

自己不会写,从解中copy了一个过来,基本思路是从0000开始找,先找一步能走到的所有(1000,-1000,0100,0-100,0010,00-10,0001,000-1),加到队列里,如果这中间找到了target,直接返回步数,如果碰到了deadend中的一个,则退出循环继续找,相当于不把deadend中的入队,也就不会接着这一个继续找,从而路径中不会包含带deadend中的坐标;那么如果找到的这一个不再deadend中,就把他添加到队列中,在下一层的循环中接着找。直到找到target,这就是最短的路径。也就是BFS广度优先搜索。

谢谢观看32 记得点赞 · 加油学习 10 · 有问题私信我 6万+

原文始发于:

主题测试文章,只做测试使用。发布者:夏枳★,转转请注明出处:http://www.cxybcw.com/119683.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code