【算法】BFS—解开密码锁的最少次数
题目
一个密码锁由 4 个环形拨轮组成,每个拨轮都有 10 个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,请给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。
解题
第一步,我们不管所有的限制条件,不管 deadends 和 target 的限制,就思考一个问题:如果让你设计一个算法,穷举所有可能的密码组合,你将怎么做?
总共有4个位置,每个位置可以向上转,也可以向下转,也就是有8种可能。比如,从 '0000' 开始,转一次,可以穷举出 '1000' ,'9000','0100','0900'······共8种密码。然后,再以这8种密码作为基础,对每种密码再转一下,穷举出所有可能······
仔细想想,这就可以抽象成一幅图,每个节点有8个相邻的节点,求的又是最短距离,这不就是典型的BFS嘛,这时框架就可以派上用场了,先写出一个“简陋”的BFS框架代码:
package BFS;import java.util.LinkedList;
import java.util.Queue;// leetcode 109 打开转盘锁
public class OpenTheTurntable {public String plusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}public String minusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}// BFS框架伪码,打印所有可能的密码public void BFS(String target) {Queue<String> queue = new LinkedList<>();queue.offer("0000");while (!queue.isEmpty()) {int sz = queue.size();// 将当前队列中的所有节点向周围扩散for (int i = 0; i < sz; i++) {String cur = queue.poll();// 判断是否到达终点System.out.println(cur);// 将一个节点的相邻节点加入队列for (int j = 0; j < 4; j++) {String up = plusOne(cur, j);String down = minusOne(cur, j);queue.offer(up);queue.offer(down);}}// 在这里增加步数}return;}}
注意:这段代码当然有很多问题,但是我们做算法题肯定不是一蹴而就的,而是从简陋到完美的。
这段BFS代码已经能够穷举所有可能的密码组合了,但是显然不能完成题目,还有如下问题需要解决:
1.会走回头路。比如,从 '0000' 拨到 '1000',但是等从队列中拿出 '1000'时,还会拨出一个 '0000',这样会产生死循环。
2.没有终止条件,按照题目要求,找到 target 就应该结束并返回拨动的次数。
3.没有对 deadends的处理,按道理这些“死亡密码”是不能出现的,也就是说遇到这些密码的时候需要跳过,不能进行任何操作。
只要按照BFS框架在对应的位置稍微修改即可修复这些问题:
package BFS;import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;// leetcode 109 打开转盘锁
public class OpenTheTurntable {public String plusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}public String minusOne(String str, int j) {char[] ch = str.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}int openLock(String[] deadends, String target) {// 记录需要跳过的死亡密码Set<String> deads = new HashSet<>();for (String s : deadends) {deads.add(s);}// 记录已经穷举过的密码,防止走回头路Set<String> visited = new HashSet<>();Queue<String> queue = new LinkedList<>();// 从起点开始启动广度优先搜索int step = 0;queue.offer("0000");visited.add("0000");while (!queue.isEmpty()) {int sz = queue.size();// 将当前队列中的所有节点向周围扩散for (int i = 0; i < sz; i++) {String cur = queue.poll();// 判断密码是否合法,是否到达终点if (deads.contains(cur)) {continue;}if (cur.equals(target)) {return step;}// 将一个节点的相邻节点加入队列for (int j = 0; j < 4; j++) {String up = plusOne(cur, j);if (!visited.contains(up)) {queue.offer(up);visited.add(up);}String down = minusOne(cur, j);if (!visited.contains(down)) {queue.offer(down);visited.add(down);}}}// 在这里增加步数step += 1;}// 如果穷举完都没有找到目标密码,那就是找不到了return -1;}public static void main(String[] args) {OpenTheTurntable openTheTurntable = new OpenTheTurntable();String[] deadends = {"8888"};int count = openTheTurntable.openLock(deadends, "0008");System.out.println(count);}}
至此,这道题目就解决了。但优化还没有结束,因为终点在哪里是知道的,所以可以用双向BFS进行优化。这里先留白,以后再补充······
相关文章:
【算法】BFS—解开密码锁的最少次数
题目 一个密码锁由 4 个环形拨轮组成,每个拨轮都有 10 个数字: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 。每个拨轮可以自由旋转:例如把 9 变为 0,0 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 0000 ,一个…...
非守护线程会阻止JVM的终止吗
非守护线程会阻止JVM的终止。在Java中,线程分为守护线程(Daemon Threads)和非守护线程(Non-Daemon Threads,也被称为用户线程)。这两种线程在JVM终止时表现出不同的行为。 非守护线程是JVM中执行程序主要逻…...
Grafana面板-linux主机详情(使用标签过滤主机监控)
1. 采集器添加labels标签区分业务项目 targets添加labels (模板中使用的project标签) … targets: [‘xxxx:9100’] labels: project: app2targets: [‘xxxx:9100’] labels: project: app1 … 2. grafana面板套用 21902 模板 演示...
MYSQL数据库基础篇——DDL
DDL:DDL是数据定义语言,用来定义数据库对象。 一.DDL操作数据库 1.查询 ①查询所有数据库 输入; 得到结果: ②查询当前数据库 输入; 例如执行下面语句: 2.创建 输入 然后展示数据库即可得到结果&…...
Springboot 集成 Swing
背景 Springboot 在 Java 给 Java 开发带来了极大的便利,那么如何把它集成到 Swing GUI 编程项目中,使得 GUI 编程更加高效?本人简单做了一下尝试,完成一个 demo ,贴出来供大家参考 具体步骤 创建一个 spring boot …...
枚举算法总结
枚举算法(Enumeration Algorithm)是一种简单而直接的算法设计策略,它通过列出问题的所有可能情况,逐一进行验证,直到找到问题的解。这种算法适用于问题的解空间不是太大,可以通过遍历所有情况来找到答案的情…...
编译 Android 11源码
参考小米6 lineageos官方编译文档:https://wiki.lineageos.org/devices/sagit/build 单独编译 framework 以LineageOS18.1(Android 11)为例: 1、在源码根目录执行: make framework-minus-apex 2、用生成的framewo…...
时间复杂度计算 递归(solve2 后续)
原帖 最近校内比较忙,更新缓慢,致歉。 这里函数每次都需要遍历 h h h 和 m m m 之间的数(复杂度 O ( n ) O(n) O(n)),所以和 solve1 略有不同。仍然假设 T ( n ) \operatorname{T}(n) T(n) 表示 m − h 1 n…...
Nginx:高性能Web服务器与反向代理的深度剖析
Nginx:高性能Web服务器与反向代理的深度剖析 Nginx(发音为“engine X”)是一款轻量级但功能强大的Web服务器和反向代理服务器,以其高并发处理能力、低内存占用和灵活的扩展性在互联网项目中得到了广泛应用。本文将深入探讨Nginx…...
JavaSE - 面向对象编程03
01 多态 01_01 认识多态 01_02 多态的好处和缺点 【1】好处:① 可以解耦合,扩展性更强,父类引用指向的子类对象可以随时切换,而后面的逻辑代码并不需要更改。 ② 使用父类引用可以作为方法的形参或返回类型来接收一切子类对象。…...
变电站缺陷数据集8307张,带xml标注和txt标注,可以直接用于yolo训练
变电站缺陷数据集8307张, 带xml标注和txt标注,可以直接用于yolo训练,赠附五个脚本 变电站缺陷数据集 数据集概述 变电站缺陷数据集是一个专门针对变电站设备和环境缺陷检测的图像数据集。该数据集包含了8307张经过标注的图像,旨…...
Redis的存储原理和数据模型
一、Redis是单线程还是多线程呢? 我们通过跑redis的代码,查看运行的程序可以得知,Redis本身其实是个多线程,其中包括redis-server,bio_close_file,bio_aof_fsync,bio_lazy_free,io_t…...
Linux 文件与目录操作命令详解
文章目录 前言创建文件1. touch2. vim 文件内容显示3. cat4. more5. less6. head7. tail 文件(目录)复制、删除和移动8. cp9. rm10. mv 压缩文件与解压缩11. gzip12. zip 和 unzip 创建目录13. mkdir 删除目录14. rmdir 改变工作目录15. cd16. pwd 显示目…...
MySQL篇(窗口函数/公用表达式(CTE))
目录 讲解一:窗口函数 一、简介 二、常见操作 1. sumgroup by常规的聚合函数操作 2. sum窗口函数的聚合操作 三、基本语法 1. Function(arg1,..., argn) 1.1. 聚合函数 sum函数:求和 min函数 :最小值 1.2. 排序函数 1.3. 跨行函数…...
408算法题leetcode--第七天
283. 移动零 283. 移动零思路:代码中注释阐述时间:O(n);空间:O(1) class Solution { public:void moveZeroes(vector<int>& nums) {// 简单思路:用一个辅助数组,将非0元素复制到里面// 双指针&…...
政务安全体系构建中的挑战
在数字化政务安全体系的构建过程中,面临着几个关键的挑战: ▋挑战一:安全防护滞后现代网络攻击技术不断演进,攻击手段日益多样化,如高级持续性威胁(APT)和勒索软件等新型攻击方式频繁出现。这些…...
基于EchoMimic加速版,可编辑标志点控制实现逼真音频驱动的肖像动画
EchoMimic 是蚂蚁集团终端技术部门开发的一项技术,旨在通过音频驱动生成逼真的肖像动画。对于那些初次接触这项技术的用户,本教程将带你逐步了解如何设置开发环境、获取项目代码、安装依赖,并最终成功运行示例生成自己的肖像动画。 文章目录 项目代码安装依赖业务拓展参数调…...
【STM32 HAL库】IIC通信与CubeMX配置
【STM32 HAL库】IIC通信与CubeMX配置 前言理论IIC总线时序图IIC写数据IIC读数据 轮询模式CubeMX配置应用示例AHT20初始化初始化函数读取说明读取函数 中断模式CubeMX配置状态机图fsm.caht20.c DMA模式CubeMX配置代码 前言 本文为笔者学习 IIC 通信的总结,基于keysk…...
iPhone 上丢失了重要的联系人?如何恢复已删除的 iPhone 联系人
丢失 iPhone 上的联系人可能会带来灾难。无论是一份很棒的新工作机会、潜在的恋爱对象,还是您一直想打电话的老朋友,如果您打开“联系人”应用时看到空白,这绝不是好事。不过,一切并非全无,仍然可以通过备份或专业软件…...
【有啥问啥】弱监督学习新突破:格灵深瞳多标签聚类辨别(Multi-Label Clustering and Discrimination, MLCD)方法
弱监督学习新突破:格灵深瞳多标签聚类辨别(Multi-Label Clustering and Discrimination, MLCD)方法 引言 在视觉大模型领域,如何有效利用海量无标签图像数据是一个亟待解决的问题。传统的深度学习模型依赖大量人工标注数据&…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
