力扣752. 打开转盘锁
Problem: 752. 打开转盘锁
文章目录
- 题目描述
- 思路及解法
- 复杂度
- Code
题目描述
思路及解法
1.用一个集合 deads 存储所有的“死锁”状态,一个集合 visited 存储所有已经访问过的状态,以避免重复访问,一个队列 q 进行广度优先搜索(BFS);并将 deadends 数组中的每个元素加入 deads 集合。
2.将初始状态 “0000” 加入队列 q 并标记为已访问。
3.进行广度优先搜索(BFS):
3.1.获取当前队列的大小 sz,表示当前层级中的节点数。
3.2.遍历当前层级中的每个节点:3.2.1.从队列中取出一个节点 cur。如果 cur 在 deads 中,则跳过该节点。如果 cur 等于目标状态 target,则返回当前步数 step。
3.2.2.生成当前状态 cur 的所有相邻状态(每一位向上拨或向下拨):对于每个相邻状态 up 和 down,如果尚未访问过,则加入队列并标记为已访问,最后使得步数step++
复杂度
时间复杂度:
O ( N × M ) O(N \times M) O(N×M);其中 N N N为状态空间0000 - 9999, M M M为每个状态的子节点树(即为8.具体到本题中可以认为时间复杂度为常量级别,同理空间复杂度也为常量级别)
空间复杂度:
O ( N ) O(N) O(N)
Code
class Solution {/*** Open the Lock** @param deadends Given string* @param target Given string* @return int*/public int openLock(String[] deadends, String target) {// Record the death password to be skippedSet<String> deads = new HashSet<>();for (String s : deadends) {deads.add(s);}// Record passwords that have been exhausted to prevent backtrackingSet<String> visited = new HashSet<>();Queue<String> q = new LinkedList<>();// Start breadth-first search from the starting pointint step = 0;q.offer("0000");visited.add("0000");while (!q.isEmpty()) {int sz = q.size();// Spreads all nodes in the current queue aroundfor (int i = 0; i < sz; ++i) {String cur = q.poll();// Determine whether the destination is reachedif (deads.contains(cur)) {continue;}if (cur.equals(target)) {return step;}// Adds the untraversed adjacents of a node to the queuefor (int j = 0; j < 4; ++j) {String up = plusOne(cur, j);if (!visited.contains(up)) {q.offer(up);visited.add(up);}String down = minusOne(cur, j);if (!visited.contains(down)) {q.offer(down);visited.add(down);}}}step++;}return -1;}/*** Flip s[j] up once** @param s Given string* @param j Current number value* @return String*/private String plusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}/*** Move s[i] down once** @param s Given string* @param j Current number value* @return String*/private String minusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}
}
相关文章:
力扣752. 打开转盘锁
Problem: 752. 打开转盘锁 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.用一个集合 deads 存储所有的“死锁”状态,一个集合 visited 存储所有已经访问过的状态,以避免重复访问,一个队列 q 进行广度优先搜索(BF…...
揭秘:义乌理阳的跨境选品师项目
在全球经济一体化的今天,跨境电商已成为各国贸易的重要组成部分,而选品师作为其中的关键角色,扮演着挑选优质商品的重要角色。在中国义乌,一家名为理阳信息咨询服务有限公司备受关注,因其据称拥有跨境选品师项目而备受…...
电视剧推荐
1、《春色寄情人》 2、《唐朝诡事录》 3、《南来北往》 4、《与凤行》 5、《利剑玫瑰》 6、《承欢记》...
ISO 19115-3:2023 关于元数据最小实例的允许命名空间的详细说明
理解说明内容 标识符(Identifier) URL: https://standards.isotc211.org/19115/-1/1/req/metadata-minimal-xml/allowed-namespaces解释: 这个 URL 标识了元数据最小实例中允许的命名空间的具体标准和规范。包含于(Included in) 要求类 4:元数据信息最小交换 (ISO 19115-…...
最新下载:CorelDraw 2023【软件附加安装教程】
简介: CorelDRAW Graphics Suite 订阅版拥有配备齐全的专业设计工具包,可以通过非常高的效率提供令人惊艳的矢量插图、布局、照片编辑和排版项目。价格实惠的订阅就能获得令人难以置信的持续价值,即时、有保障地获得独家的新功能和内容、一流…...
QT系列教程(8) QT 布局学习
简介 Qt 中的布局有三种方式,水平布局,垂直布局,栅格布局。 通过ui设置布局 我们先创建一个窗口应用程序,程序名叫layout,基类选择QMainWindow。但我们不使用这个mainwindow,我们创建一个Qt应用程序类Log…...
SpringCloud Gateway中Route Predicate Factories详细说明
官网地址:https://cloud.spring.io/spring-cloud-static/spring-cloud-gateway/2.2.1.RELEASE/reference/html/#gateway-request-predicates-factories Spring Cloud Gateway将路由匹配作为Spring WebFlux HandlerMapping基础架构的一部分。 Spring Cloud Gateway …...
计算机视觉全系列实战教程:(八)图像变换-点运算、灰度变换、直方图变换
图像变换:点运算、灰度变换、直方图变换 1.点运算(1)What(2)Why 2.灰度变换(1)What(2)Why(作用)(3)Which(有哪些灰度变换) 3.直方图修正(1)直方图均衡化 1.点运算 (1)What 通过点运算,输出图像的每个像素的灰度值仅仅取决于输入图像中相对应…...
4.MongoDB sharding Cluster 分片集群
MongoDB分片集群的介绍: 是MongoDB提供的一种可水平扩展的数据存储解决方案。 当单个MongoDB服务器无法满足数据存储需求或吞吐量要求时,可以使用分片集群来分散数据量和查询负载。分片集群的结构组成: 1.分片(shards)…...
PDF转图片工具
背景: 今天有个朋友找我:“我有个文件需要更改,但是文档是PDF的,需要你帮我改下内容,你是搞软件的,这个对你应该是轻车熟路了吧,帮我弄弄吧”,听到这话我本想反驳,我是开…...
Day 19:419. 甲板上的战舰
Leetcode 419. 甲板上的战舰 给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 ‘X’ 或者是一个空位 ‘.’ ,返回在甲板 board 上放置的 战舰 的数量。 战舰 只能水平或者垂直放置在 board 上。换句话说ÿ…...
Web前端专科实习:技能提升、实践挑战与职业展望
Web前端专科实习:技能提升、实践挑战与职业展望 在数字化时代,Web前端技术作为连接用户与互联网世界的桥梁,其重要性日益凸显。作为一名Web前端专科实习生,我有幸在这个充满机遇和挑战的领域进行实践学习。接下来,我将…...
简单脉冲动画效果实现
简单脉冲动画效果实现 效果展示 CSS 知识点 CSS 变量的灵活使用CSS 动画使用 页面整体结构实现 <div class"pulse"><span style"--i: 1"></span><span style"--i: 2"></span><span style"--i: 3"…...
apache poi 插入“下一页分节符”并设置下一节纸张横向的一种方法
一、需求描述 我们知道,有时在word中需要同时存在不同的节,部分页面需要竖向、部分页面需要横向。本文就是用java调用apache poi来实现用代码生成上述效果。下图是本文实现的效果,供各位看官查阅,本文以一篇课文为例,…...
【React】useCallback和useMemo使用指南
useCallback和useMemo是React中两个用于优化性能的Hooks。以下是它们的使用指南,分点表示并归纳了关键信息: useCallback useCallback返回一个记忆化的回调函数,该回调函数只在它的依赖项发生改变时才会更新。这对于在组件渲染之间保持稳定的引用特别有用,可以防止不必要…...
XMind软件下载-详细安装教程视频
简介 XMind是一款实用的思维导图软件,简单易用、美观、功能强大,拥有高效的可视化思维模式,具备可扩展、跨平台、稳定性和性能,真正帮助用户提高生产率,促进有效沟通及协作。中文官方网站:http://www.x…...
一个小的画布Canvas页面,记录点的轨迹
Hello大家好,好久没有更新了,最近在忙一些其他的事,今天说一下画布canvas,下面是我的代码,实现了一个点从画布的(0,0)到(canvas.width,canvas.height)的一个实…...
docker-compose教程
1. docker-compose是什么? 1. 1 简介 compose、machine 和 swarm 是docker 原生提供的三大编排工具。 简称docker三剑客。Compose 项目是 Docker 官方的开源项目,定义和运行多个 Docker 容器的应用(Defining and running multi-container Do…...
结果出乎意料!MySQL和MariaDB谁快?MySQL 8.0比MySQL 5.6快吗?
MySQL和MariaDB哪个更快?MySQL 8.0的版本和早期MySQL 5.6的版本哪个更快?这儿有个第三方的测试报告回答了这两个大家关心的问题,姚远来和大家一起解读一下。https://smalldatum.blogspot.com/2024/04/sysbench-on-small-server-mariadb-and.h…...
Alienware外星人X17R2 原装Win11系统镜像下载 带SupportAssist OS Recovery一键恢复
装后恢复到您开箱的体验界面,包括所有原机所有驱动AWCC、Mydell、office、mcafee等所有预装软件。 最适合您电脑的系统,经厂家手调试最佳状态,性能与功耗直接拉满,体验最原汁原味的系统。 原厂系统下载网址:http://w…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...

