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

双向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的差别主要在下面几点:

  1. 这里有两个起始点,一个还是原来的起点0000,还有一个是我们的目标值,从这两个点开始发散的向四周发散的寻找,所以我们需要创建两个队列和两个保存已经遍历元素的哈希集
  2. 当一个队列的元素在另一个队列里面出现,这时说明两个点之间已经“打通”,找到了最短距离
  3. 这里注意我们尽量每次让两个队列平均的进行添加,这基于BFS的特性
  4. 这里结束循环的条件是两个队列都不为空,因为只要有一个位置空,就说明两点之间不能达到

代码

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”题&#xff1a;单词接龙 “752”题&#xff1a;打开轮盘锁 这里推荐一篇力扣题解 双向BFS 这里使用打开轮盘锁的题干进行举例&#xff1a; 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字&#xff1a; ‘0’, ‘1’, ‘2’,…...

C++从入门到精通---模版

文章目录 泛型编程函数模版模版参数的匹配原则类模版类模版的定义格式类模版的实例化 总结 泛型编程 泛型编程是一种编程范式&#xff0c;旨在实现通用性和灵活性。它允许在编写代码时使用参数化类型&#xff0c;而不是具体的类型&#xff0c;从而使代码更加灵活和可重用。 在…...

Unity数据持久化之Json

Json概述 Json是什么? 全称:JavaScript对象简谱(JavaScript Object Notation) Json是国际通用的一种轻量级的数据交换格式 主要在网络通讯中用于传输数据,或本地数据存储和读取 易于人阅读和编写,同时也易于机器解析和生成,并有效地提升网络传输效率 我们一般使用Json文件来…...

LeetCode 35.搜索插入位置

给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 示例 2: 输入…...

速来get!多微信聚合聊天功能大揭秘!

随着网络时代的发展&#xff0c;微信成为了职场中不可或缺的沟通工具&#xff0c;很多人都有着多个微信号&#xff0c;而要想高效管理这些账号&#xff0c;那就少不了工具的帮忙。 通过微信管理系统&#xff0c;可以轻松实现多个微信号聚合聊天&#xff0c;提高沟通效率。 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 是一种灵活的数据类型&#xff0c;可以表示任何结构化数据。 以下是如何使用 structpb 包的一些示例&#xff1a; 创建 Struct&a…...

Vue3 + TS + Element-Plus 封装的 Dialog 弹窗组件

弹窗组件中自定义了header 增加了全屏&#xff0c;svg-icon 没有的话可能会报错&#xff0c;换成自己的图标就可以 <template><el-dialog:dialogHeight"dialogHeight":title"dialogTitle"class"dialog min-w-70"v-model"dialogVi…...

大数据技术概述_4.大数据的应用领域

1.制造业的应用 制造业目前正在向信息化和自动化的方向发展。在产品的设计、生产和销售中&#xff0c;越来越多的企业使用计算机辅助设计&#xff08;CAD&#xff09;、计算机辅助制造&#xff08;CAM&#xff09;等软件&#xff0c;数控机床、传感器等设备&#xff0c;物料需求…...

ABB RobotStudio学习记录(一)新建工作站

RobotStudio新建工作站 最近遇到 虚拟示教器和 Rapid 代码不能控制 视图中机械臂的问题&#xff0c;其实是由于机械臂和工作站不匹配。以下是解决方法。 名称版本Robot Studio6.08 新建一个”空工作站“&#xff1b; 在目标位置新建一个目标文件夹 C:\solution\test&#xff0…...

雷达通信一体化(含WCSP2023会议论文集学习)

雷达通信一体化&#xff0c;又称雷达通信融合&#xff08;RADCOM&#xff09;&#xff0c;是一种新兴的技术&#xff0c;它将雷达&#xff08;通常用于探测和跟踪目标&#xff09;和无线通信&#xff08;用于传输信息&#xff09;的功能结合在一起。这种融合技术的主要目标是提…...

特斯拉擎天柱机器人:工厂自动化的未来

随着技术的进步&#xff0c;工业自动化已经逐步进入了一个新的纪元。特斯拉最近公布的擎天柱机器人Optimus的演示&#xff0c;不仅仅展示了一个高科技机器人的能力&#xff0c;更是向我们揭示了未来工厂的可能性。 特斯拉擎天柱机器人的功能展示 马斯克在最新的演示中向我们展…...

【管理咨询宝藏93】大型制造集团数字化转型设计方案

【管理咨询宝藏93】大型制造集团数字化转型设计方案 【格式】PDF版本 【关键词】国际咨询公司、制造型企业转型、数字化转型 【核心观点】 - 235页大型制造型集团数字化转型方案设计&#xff01;细节非常详尽&#xff0c;图表丰富&#xff01; - 系统架构必须采用成熟、具有国…...

【数学建模】天然肠衣搭配问题

2011高教社杯全国大学生数学建模竞赛D题 天然肠衣&#xff08;以下简称肠衣&#xff09;制作加工是我国的一个传统产业&#xff0c;出口量占世界首位。肠衣经过清洗整理后被分割成长度不等的小段&#xff08;原料&#xff09;&#xff0c;进入组装工序。传统的生产方式依靠人工…...

Dockerfile实践java项目

目的&#xff1a;用java项目测试dockerfil部署&#xff08;前提是安装好了docker&#xff09; 部署准备文件如下 1. java项目 java项目demo地址 https://gitee.com/xiaoqu_12/dockerfileDemo.git 或者百度网盘直接下载打包好的jar包 链接&#xff1a;https://pan.baidu.com/s/…...

【管理咨询宝藏96】企业数字化转型的中台战略培训方案

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏96】企业数字化转型的中台战略培训方案 【格式】PDF版本 【关键词】SRM采购、制造型企业转型、数字化转型 【核心观点】 - 数字化转型是指&…...

【webrtc】MessageHandler 3: 基于线程的消息处理:以sctp测试为例

消息处理可以用于模拟发包处理G:\CDN\rtcCli\m98\src\net\dcsctp\socket\dcsctp_socket_network_test.cc 这个实现中,onMessage还是仅对了一种消息进行处理,就是接收则模式下,打印带宽。当然,可能程序有多个消息,分别在不同的onmessage中执行?SctpActor:以一个恒定的速率…...

redisson 使用脚本实现将一个队列的元素弹出并推入另一个队列的原子操作

脚本逻辑&#xff1a; 从队列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项目。

演示视频&#xff1a; 基于Springboot的校园新闻管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…...

Windows环境下基于CMake构建Lua

Windows环境下基于CMake构建Lua 环境&#xff01;&#xff01;&#xff01;注意&#xff1a; lua-5.4.6.tar.gz压缩包中&#xff0c;并未提供luac.c文件&#xff0c;无法构建luac.exe&#xff0c;可以从lua-5.4.5.tar.gz压缩包中拷贝使用 一、搭建基于CMake构建的Lua环境二、构…...

LLM⊗KG范式下的知识图谱问答实现框架思想阅读

分享一张有趣的图&#xff0c;意思是在分类场景下&#xff0c;使用大模型和fasttext的效果&#xff0c;评论也很逗。 这其实背后的逻辑是&#xff0c;在类别众多的分类场景下&#xff0c;尤其是在标注数据量不缺的情况下&#xff0c;大模型的收益是否能够比有监督模型的收益更多…...

ue引擎游戏开发笔记(35)——为射击添加轨道,并显示落点

1.需求分析&#xff1a; 我们只添加了开枪特效&#xff0c;事实上并没有实际的效果产生例如弹痕&#xff0c;落点等等。所以逐步实现射击的完整化&#xff0c;先从实现落点开始。 2.操作实现&#xff1a; 1.思路&#xff1a;可以这样理解&#xff0c;每次射击的过程是一次由摄…...

路由策略与路由控制

1.路由控制工具 匹配工具1&#xff1a;访问控制列表 &#xff08;1&#xff09;通配符 当进行IP地址匹配的时候&#xff0c;后面会跟着32位掩码位&#xff0c;这32位称为通配符。 通配符&#xff0c;也是点分十进制格式&#xff0c;换算成二进制后&#xff0c;“0”表示“匹配…...

JAVA版本的ATM编程问题记录

前段时间用C语言写了个银行ATM系统&#xff0c;还写了一篇文章记录了一些&#xff0c;C语言的ATM文章。后来又用IDEA写了一个JAVA版本的银行ATM。有人就会问为啥浪费这个时间写ATM呢&#xff1f;&#x1f9d0;其实是我本科代码没学好&#xff0c;所以现在想利用比较熟悉的ATM系…...

C#winfrom三层架构实现简单课程管理系统管理系统,三层架构实现增删改查

1. 项目展示 1.1登录展示 1.2添加课程信息展示 1.3课程信息管理-查询-修改-删除 1.4修改登录密码 2.项目功能介绍&#xff08;图&#xff09; 3.数据库设计 3.1 教师表设计 3.2 课程分类表 3.3 课程信息表 4. 创建样式界面 winfrom 超详细UI创建过程 实现双色球选号器UI界面…...

AI技术赋能下的视频监控方案是如何解决新能源汽车充电难问题的?

一、方案背景 刚刚结束的第十八届北京车展异常火爆&#xff0c;其中一组与汽车有关的数字让人格外关注。根据乘联会2024年4月19日公布的最新数据&#xff0c;全国乘用车市场零售达到51.6万辆&#xff0c;其中新能源车的销量约为26万辆&#xff0c;市场渗透率达到50.39%。 这意味…...

长难句打卡5.6

For H&M to offer a $5.95 knit miniskirt in all its 2,300-plus stores around the world, it must rely on low-wage overseas labor, order in volumes that strain natural resources, and use massive amounts of harmful chemicals. 翻译:H&M若要在其全球总共2…...

PDF编辑器软件常见问题(技巧)总结

目录 问题pdf高级编辑器中编辑文字时" 格式 " 如何出现? 待续、更新中 问题 pdf高级编辑器中编辑文字时" 格式 " 如何出现? shiftF4 待续、更新中 1 顿号“、” : 先使用ctrl. 再使用一遍切回 2 下标: 在数字两边加上 ~ 即可 , 21 3 上标: 2 0 2^{0} …...

Dive into Deep Learning-优化算法(1)

优化和深度学习的关系 优化是最小化损失函数&#xff0c;而深度学习的目标是在给定有限数据量的情况下寻找合适的模型&#xff0c;分别对应着训练误差和泛化误差&#xff1b;需要注意过拟合&#xff1b; 优化面临的挑战&#xff08;求解数值解&#xff09; 局部最小值&#…...

Partisia Blockchain 生态首个zk跨链DEX现已上线

在5月1日&#xff0c;由Partisia Blockchain与zkCross创建合作推出的Partisia zkCrossDEX在Partisia Blockchain生态正式上线。Partisia zkCrossDEX是Partisia Blockchain上重要的互操作枢纽&#xff0c;其融合了zkCross的zk技术跨链互操作方案&#xff0c;并利用Partisia Bloc…...