力扣752. 打开转盘锁

2024-06-13 06:28
文章标签 力扣 打开 转盘 752

本文主要是介绍力扣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. 打开转盘锁的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1056516

相关文章

ORACLE 11g 创建数据库时 Enterprise Manager配置失败的解决办法 无法打开OEM的解决办法

在win7 64位系统下安装oracle11g,在使用Database configuration Assistant创建数据库时,在创建到85%的时候报错,错误如下: 解决办法: 在listener.ora中增加对BlueAeri-PC或ip地址的侦听,具体步骤如下: 1.启动Net Manager,在“监听程序”--Listener下添加一个地址,主机名写计

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

搜狗浏览器打开CSDN博客排版错乱问题解决

之前发生过几次,不知道什么原因。 今天一直用着好好的,打开一个csdn连接,显示404,博文被删除了,于是就用百度快照打开试试,百度快照打开显示的排版很乱也没找到有用信息。 后面再浏览CSDN博客就排版错乱,显示一个大大二维码图片。 尝试删除IE缓存无效,使用谷歌浏览是好的。 基本锁定就是搜狗缓存导致的,于是找如何删除搜狗缓存   清除后恢复正常

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

我成功在本地打开了Cesium啦!

1首先下载Node.js,我是跟着这篇下载的,https://zhuanlan.zhihu.com/p/77594251,不过这后面的我没弄对Cesium环境配置也没影响。 另外:我看其他推文说,在终端写node -v和npm-v查node和npm的版本可以检测node和npm是否下载成功。 2然后我在CesiumB站官号看的教学视频,跟着下载Cesium源代码。 Cesium基础入门1-零

PageOfficeCtrl支持直接打开服务器磁盘文件

一般来说,PageOfficeCtrl控件的WebOpen方法的第一个参数是待打开文档的URL,此URL可以是相对于当前页面的相对URL,也可以是相对于整个网站根的相对URL,还可以是http开头的完整URL,但是这个URL必须是当前网站的URL,不能跨域。 现在为了更加方便开发者编程,WebOpen支持打开服务器磁盘文件。也就是说,第一个参数可以写成服务器文件的绝对磁盘路径。例如: P

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1