当前位置: 首页 > news >正文

力扣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 存储所有的“死锁”状态&#xff0c;一个集合 visited 存储所有已经访问过的状态&#xff0c;以避免重复访问&#xff0c;一个队列 q 进行广度优先搜索&#xff08;BF…...

揭秘:义乌理阳的跨境选品师项目

在全球经济一体化的今天&#xff0c;跨境电商已成为各国贸易的重要组成部分&#xff0c;而选品师作为其中的关键角色&#xff0c;扮演着挑选优质商品的重要角色。在中国义乌&#xff0c;一家名为理阳信息咨询服务有限公司备受关注&#xff0c;因其据称拥有跨境选品师项目而备受…...

电视剧推荐

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【软件附加安装教程】

简介&#xff1a; CorelDRAW Graphics Suite 订阅版拥有配备齐全的专业设计工具包&#xff0c;可以通过非常高的效率提供令人惊艳的矢量插图、布局、照片编辑和排版项目。价格实惠的订阅就能获得令人难以置信的持续价值&#xff0c;即时、有保障地获得独家的新功能和内容、一流…...

QT系列教程(8) QT 布局学习

简介 Qt 中的布局有三种方式&#xff0c;水平布局&#xff0c;垂直布局&#xff0c;栅格布局。 通过ui设置布局 我们先创建一个窗口应用程序&#xff0c;程序名叫layout&#xff0c;基类选择QMainWindow。但我们不使用这个mainwindow&#xff0c;我们创建一个Qt应用程序类Log…...

SpringCloud Gateway中Route Predicate Factories详细说明

官网地址&#xff1a;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 …...

计算机视觉全系列实战教程:(八)图像变换-点运算、灰度变换、直方图变换

图像变换&#xff1a;点运算、灰度变换、直方图变换 1.点运算(1)What(2)Why 2.灰度变换(1)What(2)Why(作用)(3)Which(有哪些灰度变换&#xff09; 3.直方图修正(1)直方图均衡化 1.点运算 (1)What 通过点运算&#xff0c;输出图像的每个像素的灰度值仅仅取决于输入图像中相对应…...

4.MongoDB sharding Cluster 分片集群

MongoDB分片集群的介绍&#xff1a; 是MongoDB提供的一种可水平扩展的数据存储解决方案。 当单个MongoDB服务器无法满足数据存储需求或吞吐量要求时&#xff0c;可以使用分片集群来分散数据量和查询负载。分片集群的结构组成&#xff1a; 1.分片&#xff08;shards&#xff09;…...

PDF转图片工具

背景&#xff1a; 今天有个朋友找我&#xff1a;“我有个文件需要更改&#xff0c;但是文档是PDF的&#xff0c;需要你帮我改下内容&#xff0c;你是搞软件的&#xff0c;这个对你应该是轻车熟路了吧&#xff0c;帮我弄弄吧”&#xff0c;听到这话我本想反驳&#xff0c;我是开…...

Day 19:419. 甲板上的战舰

Leetcode 419. 甲板上的战舰 给你一个大小为 m x n 的矩阵 board 表示甲板&#xff0c;其中&#xff0c;每个单元格可以是一艘战舰 ‘X’ 或者是一个空位 ‘.’ &#xff0c;返回在甲板 board 上放置的 战舰 的数量。 战舰 只能水平或者垂直放置在 board 上。换句话说&#xff…...

Web前端专科实习:技能提升、实践挑战与职业展望

Web前端专科实习&#xff1a;技能提升、实践挑战与职业展望 在数字化时代&#xff0c;Web前端技术作为连接用户与互联网世界的桥梁&#xff0c;其重要性日益凸显。作为一名Web前端专科实习生&#xff0c;我有幸在这个充满机遇和挑战的领域进行实践学习。接下来&#xff0c;我将…...

简单脉冲动画效果实现

简单脉冲动画效果实现 效果展示 CSS 知识点 CSS 变量的灵活使用CSS 动画使用 页面整体结构实现 <div class"pulse"><span style"--i: 1"></span><span style"--i: 2"></span><span style"--i: 3"…...

apache poi 插入“下一页分节符”并设置下一节纸张横向的一种方法

一、需求描述 我们知道&#xff0c;有时在word中需要同时存在不同的节&#xff0c;部分页面需要竖向、部分页面需要横向。本文就是用java调用apache poi来实现用代码生成上述效果。下图是本文实现的效果&#xff0c;供各位看官查阅&#xff0c;本文以一篇课文为例&#xff0c;…...

【React】useCallback和useMemo使用指南

useCallback和useMemo是React中两个用于优化性能的Hooks。以下是它们的使用指南,分点表示并归纳了关键信息: useCallback useCallback返回一个记忆化的回调函数,该回调函数只在它的依赖项发生改变时才会更新。这对于在组件渲染之间保持稳定的引用特别有用,可以防止不必要…...

XMind软件下载-详细安装教程视频

​简介 XMind是一款实用的思维导图软件&#xff0c;简单易用、美观、功能强大&#xff0c;拥有高效的可视化思维模式&#xff0c;具备可扩展、跨平台、稳定性和性能&#xff0c;真正帮助用户提高生产率&#xff0c;促进有效沟通及协作。中文官方网站&#xff1a;http://www.x…...

一个小的画布Canvas页面,记录点的轨迹

Hello大家好&#xff0c;好久没有更新了&#xff0c;最近在忙一些其他的事&#xff0c;今天说一下画布canvas&#xff0c;下面是我的代码&#xff0c;实现了一个点从画布的&#xff08;0,0&#xff09;到&#xff08;canvas.width&#xff0c;canvas.height&#xff09;的一个实…...

docker-compose教程

1. docker-compose是什么&#xff1f; 1. 1 简介 compose、machine 和 swarm 是docker 原生提供的三大编排工具。 简称docker三剑客。Compose 项目是 Docker 官方的开源项目&#xff0c;定义和运行多个 Docker 容器的应用&#xff08;Defining and running multi-container Do…...

结果出乎意料!MySQL和MariaDB谁快?MySQL 8.0比MySQL 5.6快吗?

MySQL和MariaDB哪个更快&#xff1f;MySQL 8.0的版本和早期MySQL 5.6的版本哪个更快&#xff1f;这儿有个第三方的测试报告回答了这两个大家关心的问题&#xff0c;姚远来和大家一起解读一下。https://smalldatum.blogspot.com/2024/04/sysbench-on-small-server-mariadb-and.h…...

Alienware外星人X17R2 原装Win11系统镜像下载 带SupportAssist OS Recovery一键恢复

装后恢复到您开箱的体验界面&#xff0c;包括所有原机所有驱动AWCC、Mydell、office、mcafee等所有预装软件。 最适合您电脑的系统&#xff0c;经厂家手调试最佳状态&#xff0c;性能与功耗直接拉满&#xff0c;体验最原汁原味的系统。 原厂系统下载网址&#xff1a;http://w…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...