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

个人练习-Leetcode-剑指 Offer II 109. 开密码锁

题目链接:https://leetcode.cn/problems/zlDJc7/

题目大意:给出一个四位数字的密码锁,初始状态是0000,目标是targer。每一次转动只能让一个位的轮盘转动一下(0往后转是9)。有一个vector<string> deadends,里面有很多四位的数字,如果转到其中的数字,就会死锁。我们在达到目标的过程中不能死锁。返回到达目标的最小步数,如果无法达到目标,返回-1

思路:BFS,每一步,每个数字有8个可能的变化。如果未访问且不属于死锁就加入队列。但这题还有挺多小细节的,做的时候debug了挺久…

首先,因为要得到步数,因此需要记录BFS的层数。所以BFS的while循环内还得加一层,qs记录当前队列长度,然后遍历完前qs个元素才给步数+1。

其次,【是否访问过某个数字】,实际上在其未加入队列,而在其作为邻居被访问时就可以标记了。在代码中表现为accdec就可以加入known中。当其作为q.front()再标记时,实际上可能是第二次或更多次的访问了,此时可能出现【同一数字被塞入队列多次】的情况。

比如q[1]的邻居是1234,未访问且不死锁,加入队列。而q[2]的邻居也是1234,未访问且不死锁,又加入队列。这样就塞了多次。因此,一个数字作为邻居被访问到时,就将其标记为访问过。

还有两个edge cases。

  • 如果0000属于死锁,那么直接返回-1
  • 如果target就是0000,就直接返回0

第二处是因为我们对一个数字的操作都在其【作为邻居被访问时】进行,而在队列中作为队首访问时,不再判断是否与target相等了。

                    string acc = getAcc(q.front(), idx);if (!known.count(acc) && !de.count(acc)) {known.insert(acc);if (acc == target)return step+1;elseq.push(acc);}

完整代码

class Solution {
public:string getAcc(string str, int idx) {string ret = str;if (ret[idx] == '9')ret[idx] = '0';elseret[idx]++;return ret;}string getDec(string str, int idx) {string ret = str;if (ret[idx] == '0')ret[idx] = '9';elseret[idx]--;return ret;}int openLock(vector<string>& deadends, string target) {set<string> de;set<string> known;string init("0000");for (int i = 0; i < deadends.size(); i++)de.insert(deadends[i]);queue<string> q;q.push(init);known.insert(init);if (de.count(init))return -1;if (target == init)return 0;int step = 0;while (!q.empty()) {int qs = q.size();for (int j = 0; j < qs; j++) {for (int idx = 0; idx < 4; idx++) {string acc = getAcc(q.front(), idx);if (!known.count(acc) && !de.count(acc)) {known.insert(acc);if (acc == target)return step+1;elseq.push(acc);}string dec = getDec(q.front(), idx);if (!known.count(dec) && !de.count(dec)) {known.insert(dec);if (dec == target)return step+1;elseq.push(dec);}}q.pop();}step++;}return -1;}
};

相关文章:

个人练习-Leetcode-剑指 Offer II 109. 开密码锁

题目链接&#xff1a;https://leetcode.cn/problems/zlDJc7/ 题目大意&#xff1a;给出一个四位数字的密码锁&#xff0c;初始状态是0000&#xff0c;目标是targer。每一次转动只能让一个位的轮盘转动一下&#xff08;0往后转是9&#xff09;。有一个vector<string> dea…...

四个常见的Linux面试问题

四个常见的Linux面试问题。 刚毕业要找工作了&#xff0c;只要是你找工作就会有面试这个环节&#xff0c;那么在面试环节中&#xff0c;有哪些注意事项值得我的关注呢&#xff1f;特别是专业技术岗位&#xff0c;这样的岗位询问一般都是在职的工程师&#xff0c;如何在面试环节…...

15、接口(C#)

15.1 什么是接口 接口是指定一组函数成员而不实现它们的引用类型。所以只能类和结构实现接口。 15.2 声明接口 接口声明不能包含以下成员 数据成员静态成员 接口声明只能包含以下类型的费静态成员函数声明&#xff1a; 方法事件索引器属性 这些函数成员的声明不能包含任何实…...

C++中常见的容器类使用方法举例(vector、deque、map、set)

cpp中常见的容器类有vector、list、deque、map、set、unordered_map和unordered_set。 下面将举例直接说明各个容器的使用方法。 文章目录综合示例1. vector&#xff1a;动态数组&#xff0c;支持随机访问2. list&#xff1a;双向链表&#xff0c;支持双向遍历和插入删除3. de…...

什么是强缓存和协商缓存

什么是缓存 浏览器缓存就是把一个已经请求过的Web资源&#xff08;如html页面&#xff0c;图片&#xff0c;js&#xff0c;数据等&#xff09;拷贝一份副本储存在浏览器中。缓存会根据进来的请求保存输出内容的副本。当下一个请求来到的时候&#xff0c;如果是相同的URL&#…...

算法刷题之堆

1. heapq 堆 Python 中只有最小堆&#xff1a; import heapqa [] heapq.heappush(a, 3) # 添加元素 heapq.heappush(a, 2) heapq.heappush(a, 1) while len(a): # 判断堆的长度print(heapq.heappop(a)) # 弹出堆顶元素# 将列表转换为最小堆 nums [2, 3, 1, 4, 5, 6] hea…...

javaweb导师选择系统

本文以JSP为开发技术&#xff0c;实现了一个导师选择系统。导师选择系统分为三大模块&#xff0c;包括管理员&#xff1a;学员信息管理、导师信息管理、导师选择管理、导师分布图、公告信息管理、系统管理&#xff0c;学生&#xff1a;个人资料管理、导师选择管理、导师分布图管…...

LeetCode150 逆波兰表达式求值

题目&#xff1a; 给你一个字符串数组 tokens &#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 注意&#xff1a; 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。每个操作数&#xff08;运算对象&#xff09;都可以…...

【Node.js】项目开发实战(中)

开发用户的注册和登录接口步骤1&#xff0c;打开MySQL Workbench&#xff0c;打开自己的数据库进入创建用户信息表新建 ev_users表安装并配置mysql模块安装mysql模块新建db文件夹下index.js,导入并配置mysql模块安装bcryptjs对密码进行加密处理新建/router_handler/user.js中&a…...

记录一次 New Bing 英语陪练

记录一次 New Bing 英语陪练 Now I start to speak english to chat with you . Help me find the mistake in my word and help me improve my english I’m glad you want to practice your English with me. I can help you find the mistakes in your words and help you i…...

【Python】照片居然能变素描?不会画画但是咱会代码

文章目录前言一、准备二、下载预训练模型总结前言 Photo-Sketching 一个能将照片的轮廓识别出来并将其转化为“速写”型图像的开源模块。 比如&#xff0c;这只小狗&#xff1a; 经过模型的转化&#xff0c;会变成卡通版的小狗&#xff1a; 非常秀&#xff0c;这很人工智能…...

已解决正确配置git环境变量

已解决git没有配置环境变量&#xff0c;抛出异常ERROR: Cannot find command ‘git’- do you have ‘git’ installed and in your PATH?&#xff0c;附上正确配置git环境变量的教程 文章目录报错问题报错翻译报错原因解决方法《100天精通Python》专栏推荐白嫖80g Python全栈…...

【逐步剖C】-第十章-自定义类型之结构体、枚举、联合

一、结构体 前言&#xff1a;有关结构体的声明、定义、初始化以及结构体的传参等结构体的基本使用在文章【逐步剖C】-第六章-结构体初阶中已进行了详细的介绍&#xff0c;需要的朋友们可以看看。这里主要讲解的是有关结构体的内存问题。 1. 结构体的内存对齐 &#xff08;1&…...

Windows Server 2016 中文版、英文版下载 (updated Mar 2023)

Windows Server 2016 Version 1607&#xff0c;2023 年 3 月更新 请访问原文链接&#xff1a;https://sysin.org/blog/windows-server-2016/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 本站将不定期发布官方原版风格月度更…...

Linux 4G 通信实验

目录4G 网络连接简介高新兴ME3630 4G 模块实验ME3630 4G 模块简介ME3630 4G 模块驱动修改ME3630 4G 模块ppp 联网测试前面我们学习了如何在Linux 中使用有线网络或者WIFI&#xff0c;但是使用有线网络或者WIFI 有 很多限制&#xff0c;因为要布线&#xff0c;即使是WIFI 你也得…...

华为OSPF技术详细介绍,保姆级,谁都能看懂(一)

目录 1、简介 2、OSPF基本原理 3、OSPF的特点 4、OSPF区域 5、路由器的类型 6、OSPF5种报文 7、后半部分内容 1、简介 OSPF&#xff08;Open Shortest Path First&#xff0c;开放最短路径优先&#xff09;是一个基于链路状态的内部网关协 议。目前针对IPv4协议使用的是OS…...

行人车辆检测与计数系统(Python+YOLOv5深度学习模型+清新界面)

摘要&#xff1a;行人车辆检测与计数系统用于交通路口行人及车辆检测计数&#xff0c;道路人流量、车流量智能监测&#xff0c;方便记录、显示、查看和保存检测结果。本文详细介绍行人车辆检测&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实现代码、PyQt的UI界面…...

SM3哈希算法的FPGA实现 I

SM3哈希算法的FPGA实现 I SM3哈希算法的FPGA实现 I一、什么是SM3哈希算法&#xff1f;二、SM3哈希算法的具体内容1、填充2、迭代与压缩3、计算拼凑值三、参考文档语言 &#xff1a;verilog 仿真工具&#xff1a; Modelsim EDA工具&#xff1a;quartus II 一、什么是SM3哈希算法…...

【数据结构与算法】线性表--数组

文章目录一、前言二、数组的概念三、数组的操作数组的插入数组的删除四、容器与数组五、问题&#xff1a;为何数组要从0开始编号&#xff0c;而不是1开始呢&#xff1f;六、总结一、前言 常见的数据结构如下图&#xff0c;本文主要讲解数据结构线性表--数组。 二、数组的概念 …...

剑指offer排序专题

剑指offer排序专题 jz3 数组中重复的数字描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的&#xff0c;但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如&#xff0c;如果输入长度为7的数组[…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...