力扣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);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/347988.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于Python的AI动物识别技术研究

基于Python的AI动物识别技术研究 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat、Maven 系统功能实现 系统的登录模块设计 本次设计的AI动物识别系统为了保证用户的数据安全&#xff0c;设计了登录的模块&…

永磁同步电机滞环电流控制(PI双闭环)matlab仿真模型

微♥“电击小子程高兴的MATLAB小屋”获取模型 1.滞环电流控制的原理 将给定的电流信号与反馈的电流信号进行比较&#xff0c;然后控制它俩之间的差值稳定在一个滞环范围内&#xff0c;若超出范围&#xff0c;则进行相应的调节操作。 操作如下叙述&#xff1a;假设以三相中的A相…

Python解析Word文档的自动编号

关于自动编号的知识可以参考《在 Open XML WordprocessingML 中使用编号列表》 链接&#xff1a;https://learn.microsoft.com/zh-cn/previous-versions/office/ee922775(voffice.14) python-docx库并不能直接解析出Word文档的自动编号&#xff0c;因为原理较为复杂&#xff…

Python第二语言(十、Python面向对象(上))

目录 1. 标记变量的基础类型 2. 初识对象 2.1 使用对象组织数据 3. 成员变量 3.1 类和类成员的定义 3.2 成员变量和成员方法使用 3.3 成员方法的定义语句 4. 类和对象class Clock: def ring(self): 4.1 创建类对象的语法&#xff1a;对象名 类名称() 4.2 用生活中的…

原生js写table表格固定表头

给表头添加以下属性 table表格写法参考 jquery写表格 手动合并单元格-CSDN博客 jquery写表格&#xff08;带滚动条&#xff09;_row.append($(<td>)-CSDN博客

Java SE LTS版本商用收费,有那些开源的替代方案?

&#x1f680; Java SE LTS版本商用收费&#xff0c;有那些开源的替代方案&#xff1f; 摘要 Java 对于云服务、大数据、电子商务、支付、欺诈和身份、交易等许多应用程序来说都是至关重要的语言。然而&#xff0c;Oracle 对 Java SE LTS 版本的商用收费政策引发了广泛关注和…

Django render()函数页面渲染

1&#xff0c; render() 函数 在Django框架中&#xff0c;render() 函数是一个非常有用的快捷方式&#xff0c;用于从视图函数返回一个完整的HTTP响应。它负责将给定的模板与上下文数据结合&#xff0c;渲染出最终的HTML页面&#xff0c;并返回一个HttpResponse对象。 from d…

【ArcGISPro SDK】构建多面体要素

结果展示 每个面构建顺序 代码 using ArcGIS.Core.CIM; using ArcGIS.Core.Data; using ArcGIS.Core.Geometry; using ArcGIS.Desktop.Catalog; using ArcGIS.Desktop.Core; using ArcGIS.Desktop.Editing; using ArcGIS.Desktop.Extensions; using ArcGIS.Desktop.Framework;…

Diffusers代码学习: T2I Adapter

T2I Adapter是一款轻量级适配器&#xff0c;用于控制文本到图像模型并为其提供更准确的结构指导。它通过学习文本到图像模型的内部知识与外部控制信号&#xff08;如边缘检测或深度估计&#xff09;之间的对齐来工作。 T2I Adapter的设计很简单&#xff0c;条件被传递到四个特征…

免费学习通刷课(免费高分)Pro版

文章目录 概要整体架构流程小结 概要 关于上一版的免费高分的学习通刷课&#xff0c;有很多人觉得还得登录太复杂了&#xff0c;然后我又发现了个神脚本&#xff0c;操作简单&#xff0c;可以后台挂着&#xff0c;但是还是建议调整速度到2倍速&#xff0c;然后找到你该刷的课&…

图的遍历介绍

概念 特点 无论是进行哪种遍历&#xff0c;均需要通过设置辅助数组标记顶点是否被访问来避免重复访问&#xff01;&#xff01;&#xff01;&#xff01; 类型 深度优先遍历 可以实现一次遍历访问一个连通图中的所有顶点&#xff0c;只要连通就能继续向下访问。 因此&#x…

算法专题总结链接地址

刷力扣的时候会遇到一些总结类型的题解&#xff0c;在此记录&#xff0c;方便自己以后找 前缀和 前缀和https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solutions/432752/xi-fa-dai-ni-xue-suan-fa-yi-ci-gao-ding-qian-zhui-/ 单调栈 单调栈https:…

JVM (四)GC过程

一。概述 程序计数器、虚拟机栈、本地方法栈都是随线程生灭&#xff0c;栈帧随着方法的进入和退出做入栈和出栈操作&#xff0c;实现了自动的内存清理&#xff0c;因此&#xff0c;内存垃圾回收主要集中于Java堆和方法区中。 GC整体流程示意图&#xff1a; ① 年轻代对象的移动…

Codeforces Global Round 26 D. “a“ String Problem 【Z函数】

D. “a” String Problem 题意 给定一个字符串 s s s&#xff0c;要求把 s s s 拆分成若干段&#xff0c;满足以下要求&#xff1a; 拆分出来的每一个子段&#xff0c;要么是子串 t t t&#xff0c;要么是字符 a a a子串 t t t 至少出现一次 t ≠ " a " t \ne…

简单脉冲动画效果实现

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

html+CSS+js部分基础运用18

1. 按键修饰符的应用。①姓名&#xff1a;按下回车键时调用方法输出“姓名-密码”&#xff1b;②密码&#xff1a;按下shift回车时调用方法输出“姓名密码” 图1 初始效果图 图2 按键修饰符效果图 2. 仿淘宝Tab栏切换&#xff0c;熟悉…

图解Mamba——从流体力学的角度理解Mamba

1.Transformer的问题 上面是Transformer的网络结构。对于一句话的每个单词&#xff0c;都需要跟所有单词算注意力机制。因此注意力机制的计算复杂度为 O ( n 2 ) O(n^2) O(n2)&#xff0c;其中 n n n为句子的长度&#xff0c;即单词(符号)的个数。如下图所示。 所以这也是现在…

2021 hnust 湖科大 操作系统课设 报告+原代码+指导书+流程图源文件

2021 hnust 湖科大 操作系统课设 报告原代码指导书流程图源文件 详情 目录 验证类实验&#xff1a; 1 实验一&#xff1a;Windows进程管理 1 一、 实验题目&#xff1a; 1 二、 实验目的 1 三、 实验内容 1 四、 实验结果与分析 2 五、 小结与心得体会 5 实验二&#xff1a;L…

【HarmonyOS】遇见的问题汇总

一、当前编辑的页面&#xff0c;预览打不开 1、问题说明 当前编辑的页面&#xff0c;预览打不开&#xff0c;日志提示如下&#xff1a; Route information is not configured for the current page. To avoid possible redirection issues, configure route information for…

数据结构 —— 堆

1.堆的概念及结构 堆是一种特殊的树形数据结构&#xff0c;称为“二叉堆”&#xff08;binary heap&#xff09; 看它的名字也可以看出堆与二叉树有关系&#xff1a;其实堆就是一种特殊的二叉树 堆的性质&#xff1a; 堆中某个结点的值总是不大于或不小于其父结点的值&…