当前位置: 首页 > 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环境二、构…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...

python可视化:俄乌战争时间线关键节点与深层原因

俄乌战争时间线可视化分析&#xff1a;关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一&#xff0c;自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具&#xff0c;系统分析这场战争的时间线、关键节点及其背后的深层原因&#xff0c;全面…...

【大厂机试题解法笔记】矩阵匹配

题目 从一个 N * M&#xff08;N ≤ M&#xff09;的矩阵中选出 N 个数&#xff0c;任意两个数字不能在同一行或同一列&#xff0c;求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求&#xff1a;1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...