双向BFS算法学习
双向BFS算法学习
推荐练习题
力扣“127”题:单词接龙
“752”题:打开轮盘锁
这里推荐一篇力扣题解
双向BFS
这里使用打开轮盘锁的题干进行举例:
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

分析
首先说明为什么使用双向BFS?
在这里我们可以把起点比做一个圆的圆心,我们使用BFS,就是对这个圆进行向外延伸,当延伸到目标点时,圆的面积就是时间复杂度,而我们采用双向BFS,就是从两
个点作为圆心,再进行延伸,当相交时,两个圆的面积小于只采用一个圆的面积(当目标点离起始点越远越明显)
这里我们与单向BFS的差别主要在下面几点:
- 这里有两个起始点,一个还是原来的起点0000,还有一个是我们的目标值,从这两个点开始发散的向四周发散的寻找,所以我们需要创建两个队列和两个保存已经遍历元素的哈希集
- 当一个队列的元素在另一个队列里面出现,这时说明两个点之间已经“打通”,找到了最短距离
- 这里注意我们尽量每次让两个队列平均的进行添加,这基于BFS的特性
- 这里结束循环的条件是两个队列都不为空,因为只要有一个位置空,就说明两点之间不能达到
代码
package Power;import java.util.*;public class doubleBFS {class Solution {String t, s;Set<String> set = new HashSet<>();public int openLock(String[] _ds, String _t) {s = "0000";t = _t;if (s.equals(t)) return 0;for (String d : _ds) set.add(d);if (set.contains(s)) return -1;int ans = bfs();return ans;}int bfs() {// d1 代表从起点 s 开始搜索(正向)// d2 代表从结尾 t 开始搜索(反向)Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();/** m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来* e.g.* m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋转 1 次而来* m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋转 3 次而来*/Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();d1.addLast(s);m1.put(s, 0);d2.addLast(t);m2.put(t, 0);/** 只有两个队列都不空,才有必要继续往下搜索* 如果其中一个队列空了,说明从某个方向搜到底都搜不到该方向的目标节点* e.g.* 例如,如果 d1 为空了,说明从 s 搜索到底都搜索不到 t,反向搜索也没必要进行了*/while (!d1.isEmpty() && !d2.isEmpty()) {int t = -1;if (d1.size() <= d2.size()) {t = update(d1, m1, m2);} else {t = update(d2, m2, m1);}if (t != -1) return t;}return -1;}int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {int m = deque.size();while (m-- > 0) {String poll = deque.pollFirst();char[] pcs = poll.toCharArray();int step = cur.get(poll);// 枚举替换哪个字符for (int i = 0; i < 4; i++) {// 能「正向转」也能「反向转」,这里直接枚举偏移量 [-1,1] 然后跳过 0for (int j = -1; j <= 1; j++) {if (j == 0) continue;// 求得替换字符串 str// 这里使用的方法非常巧妙,把字符为0和9的特殊情况处理了int origin = pcs[i] - '0';// 取模处理9int next = (origin + j) % 10;// 如果为0.0-1为-1,进行处理,变成9if (next == -1) next = 9;char[] clone = pcs.clone();clone[i] = (char)(next + '0');String str = String.valueOf(clone);// 如果死亡数组里面包含,就重新执行循环if (set.contains(str)) continue;// 如果已经遍历过,就重新执行循环if (cur.containsKey(str)) continue;// 如果在「另一方向」找到过,说明找到了最短路,否则加入队列if (other.containsKey(str)) {return step + 1 + other.get(str);} else {deque.addLast(str);// 添加,更新步数cur.put(str, step + 1);}}}}return -1;}}
}相关文章:
双向BFS算法学习
双向BFS算法学习 推荐练习题 力扣“127”题:单词接龙 “752”题:打开轮盘锁 这里推荐一篇力扣题解 双向BFS 这里使用打开轮盘锁的题干进行举例: 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’,…...
C++从入门到精通---模版
文章目录 泛型编程函数模版模版参数的匹配原则类模版类模版的定义格式类模版的实例化 总结 泛型编程 泛型编程是一种编程范式,旨在实现通用性和灵活性。它允许在编写代码时使用参数化类型,而不是具体的类型,从而使代码更加灵活和可重用。 在…...
Unity数据持久化之Json
Json概述 Json是什么? 全称:JavaScript对象简谱(JavaScript Object Notation) Json是国际通用的一种轻量级的数据交换格式 主要在网络通讯中用于传输数据,或本地数据存储和读取 易于人阅读和编写,同时也易于机器解析和生成,并有效地提升网络传输效率 我们一般使用Json文件来…...
LeetCode 35.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 示例 2: 输入…...
速来get!多微信聚合聊天功能大揭秘!
随着网络时代的发展,微信成为了职场中不可或缺的沟通工具,很多人都有着多个微信号,而要想高效管理这些账号,那就少不了工具的帮忙。 通过微信管理系统,可以轻松实现多个微信号聚合聊天,提高沟通效率。 1、…...
【跟我学RISC-V】(一)认识RISC-V指令集并搭建实验环境
目录 写在前面 一、RISC-V指令集简介 1、什么是ISA 2、有哪些ISA 3、CISC和RISC 4、什么是RISC-V 1. RISC 的起源 2. RISC-I 和 RISC-II 3. RISC 发展和商业化 4. RISC-V 的诞生 5、RISC-V生态的特点 6、RISC-V指令集的特点 1. 开源 2. 社区化 3. 设计简洁 4. 模…...
如何使用google.protobuf.Struct?
google.golang.org/protobuf/types/known/structpb 包提供了一种方式来创建和操作 google.protobuf.Struct 类型的数据。google.protobuf.Struct 是一种灵活的数据类型,可以表示任何结构化数据。 以下是如何使用 structpb 包的一些示例: 创建 Struct&a…...
Vue3 + TS + Element-Plus 封装的 Dialog 弹窗组件
弹窗组件中自定义了header 增加了全屏,svg-icon 没有的话可能会报错,换成自己的图标就可以 <template><el-dialog:dialogHeight"dialogHeight":title"dialogTitle"class"dialog min-w-70"v-model"dialogVi…...
大数据技术概述_4.大数据的应用领域
1.制造业的应用 制造业目前正在向信息化和自动化的方向发展。在产品的设计、生产和销售中,越来越多的企业使用计算机辅助设计(CAD)、计算机辅助制造(CAM)等软件,数控机床、传感器等设备,物料需求…...
ABB RobotStudio学习记录(一)新建工作站
RobotStudio新建工作站 最近遇到 虚拟示教器和 Rapid 代码不能控制 视图中机械臂的问题,其实是由于机械臂和工作站不匹配。以下是解决方法。 名称版本Robot Studio6.08 新建一个”空工作站“; 在目标位置新建一个目标文件夹 C:\solution\test࿰…...
雷达通信一体化(含WCSP2023会议论文集学习)
雷达通信一体化,又称雷达通信融合(RADCOM),是一种新兴的技术,它将雷达(通常用于探测和跟踪目标)和无线通信(用于传输信息)的功能结合在一起。这种融合技术的主要目标是提…...
特斯拉擎天柱机器人:工厂自动化的未来
随着技术的进步,工业自动化已经逐步进入了一个新的纪元。特斯拉最近公布的擎天柱机器人Optimus的演示,不仅仅展示了一个高科技机器人的能力,更是向我们揭示了未来工厂的可能性。 特斯拉擎天柱机器人的功能展示 马斯克在最新的演示中向我们展…...
【管理咨询宝藏93】大型制造集团数字化转型设计方案
【管理咨询宝藏93】大型制造集团数字化转型设计方案 【格式】PDF版本 【关键词】国际咨询公司、制造型企业转型、数字化转型 【核心观点】 - 235页大型制造型集团数字化转型方案设计!细节非常详尽,图表丰富! - 系统架构必须采用成熟、具有国…...
【数学建模】天然肠衣搭配问题
2011高教社杯全国大学生数学建模竞赛D题 天然肠衣(以下简称肠衣)制作加工是我国的一个传统产业,出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段(原料),进入组装工序。传统的生产方式依靠人工…...
Dockerfile实践java项目
目的:用java项目测试dockerfil部署(前提是安装好了docker) 部署准备文件如下 1. java项目 java项目demo地址 https://gitee.com/xiaoqu_12/dockerfileDemo.git 或者百度网盘直接下载打包好的jar包 链接:https://pan.baidu.com/s/…...
【管理咨询宝藏96】企业数字化转型的中台战略培训方案
本报告首发于公号“管理咨询宝藏”,如需阅读完整版报告内容,请查阅公号“管理咨询宝藏”。 【管理咨询宝藏96】企业数字化转型的中台战略培训方案 【格式】PDF版本 【关键词】SRM采购、制造型企业转型、数字化转型 【核心观点】 - 数字化转型是指&…...
【webrtc】MessageHandler 3: 基于线程的消息处理:以sctp测试为例
消息处理可以用于模拟发包处理G:\CDN\rtcCli\m98\src\net\dcsctp\socket\dcsctp_socket_network_test.cc 这个实现中,onMessage还是仅对了一种消息进行处理,就是接收则模式下,打印带宽。当然,可能程序有多个消息,分别在不同的onmessage中执行?SctpActor:以一个恒定的速率…...
redisson 使用脚本实现将一个队列的元素弹出并推入另一个队列的原子操作
脚本逻辑: 从队列1弹出元素如果存在值则推入队列2否则返回null RScript script redissonClient.getScript(); final String scriptText """local value redis.call(lpop, KEYS[1]);if value thenredis.call(rpush, KEYS[2], value);return valu…...
基于Springboot的校园新闻管理系统(有报告)。Javaee项目,springboot项目。
演示视频: 基于Springboot的校园新闻管理系统(有报告)。Javaee项目,springboot项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构…...
Windows环境下基于CMake构建Lua
Windows环境下基于CMake构建Lua 环境!!!注意: lua-5.4.6.tar.gz压缩包中,并未提供luac.c文件,无法构建luac.exe,可以从lua-5.4.5.tar.gz压缩包中拷贝使用 一、搭建基于CMake构建的Lua环境二、构…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
