Java——打开轮盘锁
题目链接
leetcode在线oj题——打开轮盘锁
题目描述
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。
题目示例
示例1:
输入:deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出:6
解释:
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的,
因为当拨动到 “0102” 时这个锁就会被锁定。
示例2:
输入: deadends = [“8888”], target = “0009”
输出:1
解释:把最后一位反向旋转一次即可 “0000” -> “0009”。
示例3:
输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出:-1
解释:无法旋转到目标数字且不被锁定。
题目提示
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 仅由若干位数字组成
解题思路
使用广度优先搜索将所有情况遍历出来
创建一个队列queue,将起始位置放进队列
首先从起始位置出发,将其从队列中拿出来,将其所有位置的字符向上波动或向下波动,如果不是死亡位置并且没有被遍历过,就放入队列中,step++
然后再将队列中所有元素都拿出来,分别对其每个位置都向上波动或向下波动,如果匹配target则直接返回step,如果不是死亡位置并且没有被遍历过就放入队列中,step++
一直重复上述操作,直到队列为空都没有找到target,说明无法达到目标,返回-1

代码
class Solution {public int openLock(String[] deadends, String target) {HashSet<String> deadDict = new HashSet<>();for (int i = 0; i < deadends.length; i++) {deadDict.add(deadends[i]);}HashSet<String> isUsed = new HashSet<>();if(deadDict.contains("0000")){return -1;}Queue<String> queue = new LinkedList<>();queue.offer("0000");isUsed.add("0000");int step = 0;while(!queue.isEmpty()){int size = queue.size();while (size != 0){String curString = queue.poll();if(curString.equals(target)){return step;}for (int i = 0; i < curString.length(); i++) {char ch1 = curString.charAt(i);char ch2 = curString.charAt(i);//向下波动或者向上波动if(ch1 == '9'){ch1 = '0';} else {ch1++;}if(ch2 == '0'){ch2 = '9';} else {ch2--;}StringBuffer sb1 = new StringBuffer(curString);StringBuffer sb2 = new StringBuffer(curString);sb1.setCharAt(i, ch1);sb2.setCharAt(i, ch2);if(!deadDict.contains(sb1.toString()) && !isUsed.contains(sb1.toString())){queue.offer(sb1.toString());isUsed.add(sb1.toString());}if(!deadDict.contains(sb2.toString()) && !isUsed.contains(sb2.toString())){queue.offer(sb2.toString());isUsed.add(sb2.toString());} }size--;}step++;}return -1;}
}
相关文章:
Java——打开轮盘锁
题目链接 leetcode在线oj题——打开轮盘锁 题目描述 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’࿰…...
JavaScript(2)
一、事件 HTML事件是发生在hTML元素上的“事情”。比如:按钮被点击、鼠标移动到元素上等… 事件绑定 方式一:通过HTML标签中的事件属性进行绑定 <input type"button" value"点我" onclick"on()"><script>fun…...
FFMPEG 安装教程windowslinux(CentOS版)
ps: 从笔记中迁移至blog 版本概述 Windows 基于win10 Linux 基于CentOS 7.6 一.Windows安装笔记 1.下载安装 https://ffmpeg.org/download.html 2 解压缩,拷贝到需要目录,重命名 3 追加环境变量 echo %PATH%setx /m PATH "%PATH%;F:\dev_tools\…...
【虹科案例】虹科任意波形发生器在量子计算中的应用
虹科AWG在量子计算中的应用精度在研究中始终很重要,很少有研究领域需要比量子研究更高的精度。奥地利因斯布鲁克大学的量子光学和量子信息研究所需要一个任意波形发生器(AWG)来为他们的研究生成各种各样的信号。01无线电频率第一个应用是在射…...
【强化学习】强化学习数学基础:随机近似理论与随机梯度下降
强化学习数学基础:随机近似理论与随机梯度下降Stochastic Approximation and Stochastic Gradient Descent举个例子Robbins-Monro algorithm算法描述举个例子收敛性分析将RM算法用于mean estimationStochastic gradient descent算法描述示例和应用收敛性分析收敛模式…...
ThreadLocal 学习常见问题
ThreadLocal 这个此类提供线程局部变量。这些变量不同于通常的对应变量,因为每个访问一个变量的线程(通过 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是希望将状态与线程(例如,用户 ID 或事务 ID)关联的类中的私有静态字段。使…...
文件包含漏洞1 | iwebsec
文章目录00-文件包含漏洞原理环境01-本地文件包含读取敏感文件信息配合文件上传getshell配合日志文件getshell配合SSH日志配合运行环境00-文件包含漏洞原理 为什么要文件包含? 为什么会有文件包含漏洞? 因为将被包含的文件设置为变量,用来进行动态调用…...
基于MindAR实现的网页端WebAR图片识别叠加动作模型追踪功能(含源码)
前言 由于之前一直在做这个AR/VR 相关的功能开发,大部分的时候实现方式都是基于高通Vuforia或者EasyAR等基于Unity3d的引擎的开发,这样开发的程序大部分都是运行在APP上,安卓或者ios的开发也能一次性搞定。不过当时大部分的需求都是需要在网…...
ssh 远程连接方式总结
SSH 概述 SSH(安全外壳协议 Secure Shell Protocol,简称SSH)是一种加密的网络传输协议,用于在网络中实现客户端和服务端的连接,典型的如我们在本地电脑通过 SSH连接远程服务器,从而做开发,Wind…...
springboot+mybatisPlus简单实现数据分页显示
项目地址:https://gitee.com/flowers-bloom-is-the-sea/geo_demo/tree/v1.0/ 这个项目的测试是可以的。 先来查看一些tb_shop表: id name x y ------ ------ ------ --------里面是空数据,那么现在对数据里插入一些数据…...
axios的基本使用
axios 安装axios npm install axios 使用时先导入 import axios from ‘axios’ axios请求方式 axios支持多种请求方式 axios(config) axios.request(config) axios.get(url[, config]) axios.head(url, [, config]) axios.post(url[, data[, config]]) axios.put(url[, dat…...
核心 Android 调节音量的过程
核心 Android 系统提供的调节音量的方法 核心 Android 系统提供了多种调节音量的方法,这些方法主要包括如下这些。 如在 Android Automotive 调节音量的过程 中我们看到的,CarAudioService 最终在 CarAudioDeviceInfo 中 (packages/services/Car/servi…...
用C/C++制作一个简单的俄罗斯方块小游戏
用C/C制作一个简单的俄罗斯方块小游戏 用C/C制作一个简单的俄罗斯方块小游戏 0 准备1 游戏界面设计 1.1 界面布局1.2 用 EasyX 显示界面1.3 音乐播放 2 方块设计 2.1 方块显示2.2 随机生成一个方块2.3 方块记录 3 方块移动和旋转 3.1 方块的移动3.2 方块的旋转3.3 方块的碰撞和…...
使用免费负载生成器swingbench对oracle数据库进行压力测试(测试Oracle的功能或评估性能)
1.Swingbench 简介 Swingbench 是一个免费负载生成器(和基准测试),旨在对 Oracle 数据库 进行压力测试。目前最新版本 Swingbench 2.6。 SwingBench 由负载生成器,协调器和集群概述组成。该软件可以生成负载 并绘制交易/响应时间…...
【预告】ORACLE Primavera P6 v22.12 虚拟机发布
引言 离ORACLE Primavera P6 EPPM最新系统 v22.12已过去了3个多月,应盆友需要,也为方便大家体验,我近日将构建最新的P6的虚拟环境,届时将分享给大家,最终可通过VMWare vsphere (esxi) / workstation 或Oracle virtua…...
机器学习100天(四十):040 线性支持向量机-公式推导
《机器学习100天》完整目录:目录 机器学习 100 天,今天讲的是:线性支持向量机-公式推导! 首先来看这样一个问题,在二维平面上需要找到一条直线划分正类和负类。 我们找到了 A、B、C 三条直线。这三条直线都能正确分类所有训练样本。但是,哪条直线最好呢?直观上来看,我…...
失败经验之震荡玩家往往死于趋势市场
亏损,是从去年开始的吧。 尤其是去年,仅仅一年,就亏掉了自从交易以来的所有盈利。 现在,我甚至不敢去计算具体的亏损金额。 保守估计,已经亏损100万左右。 现在回想,似乎也是必然。 交易本来就是一个走…...
应用层与传输层~
文章目录应用层自定义应用层协议什么是自定义应用层协议自定义方式运输层运输层概述运输层特点运输层协议UDP协议UDP的特点UDP首部格式校验规则TCP协议TCP的特点TCP协议段格式TCP的性质确认序号超时重传连接管理三次握手四次挥手TCP的状态滑动窗口流量控制拥塞控制延迟应答捎带…...
IO文件操作
认识文件 狭义的文件 存储在硬盘上的数据,以“文件"为单位,进行组织 常见的就是普通的文件 (文本文件,图片, office系列,视频,音频可执行程序…)文件夹也叫做"目录" 也是一种特殊的文件。 广义的文件 操作系统,是要负责管理软硬件资源,操作系统(…...
【构建工具】webpack 3、4 升级指南,摆脱低版本的困扰
一、依赖处理 1.升级通用依赖 借用 ncu 库实现,帮你改写需要升级的package.json 然后再 npm install ncu -u <packages> # 可以指定依赖 ncu # 升级全部依赖大概列了下升级的效果 add-asset-html-webpack-plugin ^2.1.3 → ^5.0.2 clean-webpack-…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
