首页 > 其他分享 >752. 打开转盘锁(中)

752. 打开转盘锁(中)

时间:2023-12-22 09:56:24浏览次数:25  
标签:q1 752 ch cur 队列 int str 打开 转盘

目录

题目

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

题解:BFS

  • 只转一下锁,有四个位置,每个位置都可以往上或下转,共8种密码,每个结点有8个相邻的结点
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def plusOne(s: str, j: int) -> str:# 向上拨动一位
            ch = list(s)
            if ch[j] == '9':#ch[j] 表示字符串 ch 中索引为 j 的字符
                ch[j] = '0'
            else:
                ch[j] = str(int(ch[j]) + 1)#将字符转换为整数+1再转换回字符串类型
            return ''.join(ch)#将列表 ch 中的所有元素连接起来形成一个字符串。

        def minusOne(s: str, j: int) -> str:# 向下拨动一位
            ch = list(s)
            if ch[j] == '0':
                ch[j] = '9'
            else:
                ch[j] = str(int(ch[j]) - 1)
            return ''.join(ch)
        q = []  # 用一个列表做队列
        v = []  # 记录走过的路
        q.append('0000')  # 把起点放入队列
        v.append('0000')
        step = 0  # 记录扩散步数
        while q:  # 当队列不为空时
            size = len(q)
            # 将当前队列中的所有节点向四周扩散
            for _ in range(size):
                cur = q.pop(0)  # 从头部取出节点
                if cur in deadends:  # 判断是否到死亡数字
                    continue
                if cur == target:   # 判断是否到达终点
                    return step

                for i in range (4):  # 将cur的相邻节点加入队列
                    up = plusOne(cur,i) # 向上拨动一位
                    if up not in v:     # 避免重复访问
                        q.append(up)
                        v.append(up)
                    down = minusOne(cur,i) # 向下拨动一位
                    if down not in v:      # 避免重复访问
                        q.append(down)
                        v.append(down)
            step += 1  # 增加步数
        return -1      # 无法达到目标,返回-1
  • 超出时间限制

题解:双向BFS

  • 当知道终点的时候,可以使用双向的BFS。传统的BFS是从起点向四周扩散,遇到终点时停止;双向的BFS则从起点和终点同时开始扩散,当两边有交集的时候停止。
  • 不再使用队列,用集合方便快速判断两个集合是否有交集。
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def plusOne(s: str, j: int) -> str:# 向上拨动一位
            ch = list(s)
            if ch[j] == '9':#ch[j] 表示字符串 ch 中索引为 j 的字符
                ch[j] = '0'
            else:
                ch[j] = str(int(ch[j]) + 1)#将字符转换为整数+1再转换回字符串类型
            return ''.join(ch)#将列表 ch 中的所有元素连接起来形成一个字符串。

        def minusOne(s: str, j: int) -> str:# 向下拨动一位
            ch = list(s)
            if ch[j] == '0':
                ch[j] = '9'
            else:
                ch[j] = str(int(ch[j]) - 1)
            return ''.join(ch)
        q1 = set()  # 用一个集合做队列
        q2 = set()  # 用一个集合做队列
        v = set()  # 记录走过的路
        q1.add('0000')  # 把起点放入队列
        q2.add(target)  # 把起点放入队列
        v.add('0000')
        step = 0  # 记录扩散步数
        while q1 and q2:  # 当队列不为空时
            if (len(q1)>len(q2)):# 集合中元素越多,扩散后就越多,所有可以始终从较小的队列开始扩散(这两行可以不加,只是一个小的trick)
                q1,q2=q2,q1
            temp=set()
            size = len(q1)
            # 将当前队列中的所有节点向四周扩散
            for _ in range(size):
                cur = q1.pop()  # 从头部取出节点
                if cur in deadends:  # 判断是否到死亡数字
                    continue
                if cur in q2:   # 判断是否到达终点
                    return step
                v.add(cur)
                for i in range (4):  # 将cur的相邻节点加入队列
                    up = plusOne(cur,i) # 向上拨动一位
                    if up not in v:     # 避免重复访问
                        temp.add(up)
                    down = minusOne(cur,i) # 向下拨动一位
                    if down not in v:      # 避免重复访问
                        temp.add(down)
            step += 1  # 增加步数
            q1=q2
            q2=temp
        return -1      # 无法达到目标,返回-1

标签:q1,752,ch,cur,队列,int,str,打开,转盘
From: https://www.cnblogs.com/lushuang55/p/17920073.html

相关文章

  • 解决GNU Radio的内嵌代码块无法打开代码编辑器
    摘要解决GNURadio的内嵌代码块无法打开编辑器的问题.通过修改py脚本实现使用VSCode编辑内嵌代码.问题描述环境:系统macOS13.5GNURadioCompanion3.10.8.0(Python3.10.13)代码块选择应用程序是空的选择应用程序是空的实现修改/Users/workspace/rad......
  • win7系统每个工作日8点打开系统声音,下午5点半关闭
    通过启用或禁用音频服务来实现启用音频服务脚本(enable_audio.bat): netstartaudiosrv禁用音频服务脚本(disable_audio.bat):netstopaudiosrv创建计划任务打开开始菜单,搜索并打开“任务计划程序”。选择“创建任务...”而非“创建基本任务...”,以便获取更多配置选......
  • PDF文件打开时,总是定位到某个特定页面
    PDF文件正常打开时,会默认显示第一页,或者默认显示上次关闭时停留的页面。但是某个PDF特别奇怪,打开它时,总是显示在某个特定页面。当我把这个页移动到开头时,打开文档就定位到开头;当我把这个页移动到结尾时,打开文档就定位到结尾;当我把它移动到第3页,打开文档就定位到第3页。但是我......
  • VMware Ubuntu虚拟机打开报错问题
    问题描述昨天虚拟机卡死,我把VMwareWorkstation的进程用任务管理器杀掉了,今天重新打开虚拟机却发现以下报错报错内容另一个程序已锁定文件的一部分,进程无法访问打不开磁盘“E:\VMware\Linux\ubuntu-18.04.6\ubuntu-18.04.6.vmdk”或它所依赖的某个快照磁盘。模块“Disk”启......
  • python代码自动打开浏览器并输入相应的内容后搜索
    需求描述:使用python代码实现自动打开浏览器,之后进入百度,输入‘小姐姐’,查看结果1.安装selenium,直接安装4.0版本。pipinstallselenium==4.0看到successful字样就安装成功了2.代码实现#@File:自动化测试.py#author:蜜蜂#Time:2023/12/1917:06importtimefromseleniumimpo......
  • qt打开项目缺少ui_文件,使用手动生成(转)
    打开项目看到,缺少ui_myMainWindow.h文件,它是和myMainWindow.ui相对应的,所以我们需要手动生成对应的ui_文件。步骤如下:使用uic.exe来生成,如果在系统变量Path中设置了qt的bin目录,那么就可以直接使用uic.exe。使用方法是:在myMainWindow.ui所在文件夹的空白处点击右键,选择【在终端中......
  • 国产显卡如何正确打开 —— Windows平台下使用驱动精灵为国产显卡更新驱动(兆芯平台)
    买了一个国产的电脑,全国产,CPU慢些也就忍了,软件兼容性差、稳定性差也忍了,大不了就用来上网看电影嘛,关键问题是这个国产显卡放电影居然有些卡,播放电影的时候存在明显的卡顿感,这简直是把国产电脑在我脑海中唯一的用处也给堵上了。最近想着用用Windows的11代操作系统,尝尝鲜,但是手上没......
  • NX 2306 打开文件-无法加载从重用库插入的标准件(使用当前搜索选项找不到文件,部件已卸
    【写在每个笔记前面:个人学习记录,如有错误,烦请指正,不胜感激。】   (今日内容源于  NX网-老叶)重新打开装配体,加载异常,有如下警告首先明确如下两点:1、组件的文件路径未改动2、组件的文件名称未改动其次最后一点:☆:装配加载选项:修改为“按照保存的”,官方解释如下图右。......
  • 带领新手小白如何在SSH终端打开图形化界面!!!
    写在前面博主最近在做一个类似于网络聊天室的东西,需要在服务器端把哪个客户机加入了、客户机之间发送的什么消息打印出来。本来以为是个挺简单的东西,没想到卡在了第一步!!!linux本身并没有自带图形化界面,需要我们进行设置。博主使用的SSH终端是MobaXterm。X11转发首先需要设置X11......
  • 电脑上软件双击打开没反应
    今天遇到一个很少见的问题,双击电脑上快捷方式没有反应。一般都会有个提示,根据提示判断问题。去安装路径下尝试打开也没用,判断不是快捷方式的原因。管理员权限打开也没用,杀毒软件退出也没用,也不是权限的问题。连接的官网也可以打开,不是网络原因。几个常见的原因也被排除了。最......