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

java数据结构与算法刷题-----LeetCode127. 单词接龙

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

    • 广度优先+双分裂蛇

在这里插入图片描述

广度优先+双分裂蛇

解题思路:时间复杂度O( n ∗ c ∗ 26 n*c*26 nc26),n是字典中单词个数,c是单词的长度,26是26个字母,空间复杂度O( n ∗ c ∗ 26 n*c*26 nc26)
  1. 此题就是求二维图起点到终点的最短路径问题。而这个问题本身只是中等难度。但是为什么这道题是困难难度呢?因为这道题太抽象了,虽然是考查图的最短路径,但是题目描述很难让人联想到图,所以以后只要遇到求最短路径的题,看看能不能抽象成二维图,能就说明考察的分裂蛇知识点。
  2. 这道题只要抽象成图的数据结构,就退化为1091题了,只要1091题掌握了,这道题就只需要你将图的逻辑抽象出来就可以了。不过这道题的处理稍微有些不同.
🏆LeetCode1091. 二进制矩阵中的最短路径https://blog.csdn.net/grd_java/article/details/137090602
  1. 将题目给的字典中每个单词都抽象成一个顶点,而两个单词如果只有一个字母不一样,就抽象成这两个单词之间有一条边。这样就有了图数据结构了。
  2. 然后创建两个Set集合(一般是用队列,但是这道题用队列反而不太好做,因为我们需要确定当前A队列遇到的新单词是否在另一个队列中)。一个从头开始走,一个从终点开始走。
  1. 因为我们是抽象的图数据结构,不知道顶点和边的关系,所以我们需要每遇到一个单词,就替换它里面每个字母生成一个新单词,只要这个新单词是题目所给字典中的单词,就说明当前这个单词和这个新单词都是存在于字典中的,且两者之间有一条边。因此这些新单词就是当前结点的下一个广度优先遍历对象

因为两个单词如果只有一个字母不一样,就抽象成这两个单词之间有一条边,但是题目本身没给这个关系,我们只能一个个枚举(修改这个单词中单个字母),时间复杂度是O( c ∗ 26 c*26 c26),c是这个单词由几个字母组成

  1. 当首尾两个集合相遇的一瞬间,其代表的路径就是最短路径(双分裂蛇的特点)。
代码:官方增加了测试用例,相同的算法原来是21ms超越100%,现在只能到达22ms,已经无法超越100%了

在这里插入图片描述

class Solution {//将单词抽象成图结构,然后通过双向广度优先算法求最短路径//每个单词都是一个顶点,如果两个单词只有一个字母不同,则他俩直接有一条边public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 将单词列表转换为集合,便于快速检查单词是否存在于列表中Set<String> wordSet = new HashSet<>(wordList);if (!wordSet.contains(endWord)) return 0; // 如果结束单词不在列表中,无法完成转换,直接返回0// 使用两个集合(代替队列)分别存储从开始和结束单词出发的广度优先搜索的边界。双向广度优先,一个从起点,一个从终点找Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>();int len = 1; // 初始化路径长度为1,因为开始单词也计入路径int strLen = beginWord.length(); // 单词的长度,假设所有单词长度相同HashSet<String> visited = new HashSet<>(); // 记录已访问的单词,避免重复处理,我们不更改原表,使用新的表来标志某个单词是否已经访问// 将开始和结束单词加入对应的集合beginSet.add(beginWord);endSet.add(endWord);// 只要两个集合都非空,就继续执行双向搜索while (!beginSet.isEmpty() && !endSet.isEmpty()) {// 总是选择较小的集合进行扩展,以减少下一轮处理的单词数量if (beginSet.size() > endSet.size()) {Set<String> temp = beginSet;beginSet = endSet;endSet = temp;}Set<String> temp = new HashSet<>(); // 用于存储下一轮扩展的结果,如果是队列就不需要这步for (String word : beginSet) {//遍历当前队列(集合)中结点,让他们走一步,每次只走一步char[] chs = word.toCharArray();// 尝试更改当前单词的每一个字符,看看是否可以接龙for (int i = 0; i < chs.length; i++) {for (char c = 'a'; c <= 'z'; c++) {//用a到z依次替换char old = chs[i]; // 保存原始字符chs[i] = c;//用a-z依次替换i位置字符String target = String.valueOf(chs); // 生成新单词// 如果新单词在另一端集合中,说明找到了最短路径if (endSet.contains(target)) return len + 1;// 如果新单词未访问且存在于单词列表中,则加入下一轮搜索if (!visited.contains(target) && wordSet.contains(target)) {temp.add(target);visited.add(target); // 标记为已访问}chs[i] = old; // 恢复原始字符,以便下一次修改}}}beginSet = temp; // 更新beginSet为下一轮搜索的边界len++; // 每完成一轮双向搜索,路径长度加1,因为我们规定,每次只走一步}return 0; // 如果无法连接开始和结束单词,返回0}
}

相关文章:

java数据结构与算法刷题-----LeetCode127. 单词接龙

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 广度优先双分裂蛇 广度优先双分裂蛇 解题思路&#xff1a;时间复…...

pytorch中的torch.nn.Linear

torch.nn.Linear是pytorch中的线性层&#xff0c;应该是最常见的网络层了&#xff0c;官方文档&#xff1a;torch.nn.Linear。 torch.nn.Linear(in_features, out_features, biasTrue, deviceNone, dtypeNone)其中&#xff0c;in_features表示输入的维度&#xff1b;out_featu…...

03-MySQl数据库的-用户管理

一、创建新用户 mysql> create user xjzw10.0.0.% identified by 1; Query OK, 0 rows affected (0.01 sec) 二、查看当前数据库正在登录的用户 mysql> select user(); ---------------- | user() | ---------------- | rootlocalhost | ---------------- 1 row …...

知乎:多云架构下大模型训练,如何保障存储稳定性?

知乎&#xff0c;中文互联网领域领先的问答社区和原创内容平台&#xff0c;2011 年 1 月正式上线&#xff0c;月活跃用户超过 1 亿。平台的搜索和推荐服务得益于先进的 AI 算法&#xff0c;数百名算法工程师基于数据平台和机器学习平台进行海量数据处理和算法训练任务。 为了提…...

JWFD流程图转换为矩阵数据库的过程说明

在最开始设计流程图的时候&#xff0c;请务必先把开始节点和结束节点画到流程图上面&#xff0c;就是设计器面板的最开始两个按钮&#xff0c;先画开始点和结束点&#xff0c;再画中间的流程&#xff0c;然后保存&#xff0c;这样提交到矩阵数据库就不会出任何问题&#xff0c;…...

GT收发器第一篇_总体结构介绍

文章目录 前言GT收发器介绍 前言 之前写过一篇简单介绍GT的文章https://blog.csdn.net/m0_56222647/article/details/136730026&#xff0c;可以先通过这篇文章对整体进行简单了解一下。 GT收发器介绍 参考xilinx手册ug476 对于7系列的FPGA&#xff0c;共有3个系列&#xf…...

[图像处理] MFC载入图片并进行二值化处理和灰度处理及其效果显示

文章目录 工程效果重要代码完整代码参考 工程效果 载入图片&#xff0c;并在左侧显示原始图片、二值化图片和灰度图片。 双击左侧的图片控件&#xff0c;可以在右侧的大控件中&#xff0c;显示双击的图片。 初始画面&#xff1a; 载入图片&#xff1a; 双击左侧的第二个控件…...

centos7.5 安装gitlab-ce (Omnibus)

一、安装前置依赖 # 安装基础依赖 $ sudo yum -y install policycoreutils openssh-server openssh-clients postfix# 启动 ssh 服务 & 设置为开机启动 $ sudo systemctl enable sshd & sudo systemctl start sshd二、安装gitlab rpm包 # 下载并执行社区版脚本 curl …...

深入理解MapReduce:从Map到Reduce的工作原理解析

当谈到分布式计算和大数据处理时&#xff0c;MapReduce是一个经典的范例。它是一种编程模型和处理框架&#xff0c;用于在大规模数据集上并行运行计算任务。MapReduce包含三个主要阶段&#xff1a;Map、Shuffle 和 Reduce。 ** Map 阶段 ** Map 阶段是 MapReduce 的第一步&am…...

初始Java篇(JavaSE基础语法)(5)(类和对象(上))

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 面向对象的初步认知 面向对象与面向过程的区别 类的定义和使用 类的定义格式 类的实例化 this引用 什么是this引用&#xff1f; this引用…...

机器人---人形机器人之技术方向

1 背景介绍 在前面的文章《行业杂谈---人形机器人的未来》中&#xff0c;笔者初步介绍了人形机器人的未来发展趋势。同智能汽车一样&#xff0c;它也会是未来机器人领域的一个重要分支。目前地球上最高智慧的结晶体就是人类&#xff0c;那么人形机器人的未来会有非常大的发展空…...

MySQL MHA高可用数据库

文章目录 MySQL MHA高可用数据库搭建MySQL MHA模拟故障故障修复&#xff1a; MySQL MHA高可用数据库 MHA&#xff08;MySQL High Availability&#xff09;是一个开源的高可用解决方案&#xff0c;用于实现MySQL主从复制集群的故障自动切换。MHA的主要目的是确保MySQL数据库集…...

LVS(Layout versus schematic)比的是什么?

概述 LVS不是一个简单地将版图与电路原理图进行比较的过程&#xff0c;它需要分两步完成。第一步“抽取”&#xff0c;第二步“比较”。首先根据LVS提取规则&#xff0c;EDA 工具从版图中抽取出版图所确定的网表文件&#xff1b;然后将抽取出的网表文件与电路网表文件进行比较…...

从0开始搭建基于VUE的前端项目(三) Vuex的使用与配置

准备与版本 vuex 3.6.2(https://v3.vuex.vuejs.org/zh/)概念 vuex是什么? 是用作 【状态管理】的 流程图如下 state 数据状态,成员是个对象 mapState 组件使用this.$store.state.xxx获取state里面的数据 getters 成员是个函数,方便获取state里面的数据,也可以加工数据 ma…...

python统计分析——双样本均值比较

参考资料&#xff1a;python统计分析【托马斯】 1、配对样本t检验 在进行两组数据之间的比较时&#xff0c;有两种情况必须区分开。在第一种情况中&#xff0c;同一对象在不同时候的两个记录值进行相互比较。例如&#xff0c;用学生们进入初中时的身高和他们一年后的身高&…...

三台电机的顺启逆停

1&#xff0c;开启按钮输入信号是 电机一开始启动&#xff0c;5秒回电机2启动 &#xff0c;在5秒电机三启动 关闭按钮输入时电机3关闭 &#xff0c;5秒后电机2关闭 最后电机一关闭 2&#xff0c;思路开启按钮按下接通电机1 并且接通定时器T0 定时器T0 到时候接通电机2 并且开…...

彩虹外链网盘界面UI美化版超级简洁好看

彩虹外链网盘&#xff0c;是一款PHP网盘与外链分享程序&#xff0c;支持所有格式文件的上传&#xff0c;可以生成文件外链、图片外链、音乐视频外链&#xff0c;生成外链同时自动生成相应的UBB代码和HTML代码&#xff0c;还可支持文本、图片、音乐、视频在线预览&#xff0c;这…...

企业微信知识库:从了解到搭建的全流程

你是否也有这样的疑惑&#xff1a;为什么现在的企业都爱创建企业微信知识库&#xff1f;企业微信知识库到底有什么用&#xff1f;如果想要使用企业微信知识库企业应该如何创建&#xff1f;这就是我今天要探讨的问题&#xff0c;感兴趣的话一起往下看吧&#xff01; | 为什么企业…...

【华为OD机试C++】合并表记录

《最新华为OD机试题目带答案解析》:最新华为OD机试题目带答案解析,语言包括C、C++、Python、Java、JavaScript等。订阅专栏,获取专栏内所有文章阅读权限,持续同步更新! 文章目录 描述输入描述输出描述示例1示例2代码描述 数据表记录包含表索引index和数值value(int范围的…...

uniapp中使用u-popup组件导致的弹框下面的页面可滑动现象

添加代码&#xff1a; touchmove.stop.prevent"()>{}"...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...