上海网站建设 app开发/网络整合营销4i原则是指
文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:示例1为例,hit到达cog的路线不止一条,如何找到最短是关键。广度优先搜索是一圈一圈的搜索过程,一旦找到了结果,一定是最短的。本题也只需要最短转换序列的数目而不需要具体的序列,因此不用去关心下图中线是如何连在一起的。因此最终选择广搜,只要差一个字符说明序列之间是连接的。
- 本题还是一个无向图,需要用到标记位,标记节点是否走过,否则会陷入死循环。为此我们引入一个unordered_map<string, int> visitMap类型的地图,记录word是否被访问过,key值为单词,value为beginWord到该单词的路径长度。
- 集合是数组类型的,提前转成集合set类型,查找更快。
根据单词的长度,每次替换其中一个单词,需要用到两个循环,一个循环选择单词中替换的字符位置,另一个用来选择26个字母中的其中一个。然后在单词集合中查找是否存在替换之后的新单词,如果找到将其加入visitMap中。如果新单词是endWord,那么直接放回path+1。path代表路径长度。
程序如下:
// 127、单词接龙-深度优先搜索
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 转成uset类型,查找更快if (wordSet.find(endWord) == wordSet.end()) return 0; // endWord没有在单词集合中出现,直接返回0unordered_map<string, int> visitMap; // 记录word是否被访问过,key值为单词,value为beginWord到该单词的路径长度queue<string> que; visitMap.insert(pair<string, int>(beginWord, 1));que.push(beginWord);while (!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 路径长度for (int i = 0; i < word.size(); i++) {string newWord = word; // 用一个新单词替换word,每次置换一个字母for (int j = 0; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endWord) return path + 1; // 找到endif (wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()) { // newWord出现在wordSet中,且没有访问过visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}return 0;}
};
复杂度分析:
-
时间复杂度: O ( N × C ) O(N \times C) O(N×C),N为wordList长度,C为单词长度。字符串数组转化成umap字符串类型需要 O ( N ) O(N) O(N)。最坏情况下,遍历到wordList最后一个元素才会找到endWord,while循环中的一些操作(如visitMap插入元素和que队列插入、弹出元素复杂度)为 O ( N ) O(N) O(N)。两个for循环的复杂度为 O ( 26 × C ) O(26 \times C) O(26×C)。因此最终的复杂度为 O ( N × C ) O(N \times C) O(N×C)。
-
空间复杂度: O ( N × C ) O(N \times C) O(N×C)。
三、完整代码
// 127、单词接龙-深度优先搜索
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 转成uset类型,查找更快if (wordSet.find(endWord) == wordSet.end()) return 0; // endWord没有在单词集合中出现,直接返回0unordered_map<string, int> visitMap; // 记录word是否被访问过,key值为单词,value为beginWord到该单词的路径长度queue<string> que; visitMap.insert(pair<string, int>(beginWord, 1));que.push(beginWord);while (!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 路径长度for (int i = 0; i < word.size(); i++) {string newWord = word; // 用一个新单词替换word,每次置换一个字母for (int j = 0; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endWord) return path + 1; // 找到endif (wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()) { // newWord出现在wordSet中,且没有访问过visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}return 0;}
};
end
相关文章:

【算法与数据结构】127、LeetCode单词接龙
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:示例1为例,hit到达cog的路线不止一条,如何找到最短是关键。广度优先搜索是一圈…...

CAN——创建一个数据库DBC文件
一、创建一个工程 file——new——can 500kbaud1ch 得到一个工程文件.cfg 二、实现两个节点通讯 can networks 三、创建数据库DBC tool——candbeditor——file——creatdatabase——cantemplate.dbc 1.建数值表 view——value tables——空白处右击add—— definition 定…...

(十三)【Jmeter】线程(Threads(Users))之tearDown 线程组
简述 操作路径如下: 作用:在正式测试结束后执行清理操作,如关闭连接、释放资源等。配置:设置清理操作的采样器、执行顺序等参数。使用场景:确保在测试结束后应用程序恢复到正常状态,避免资源泄漏或对其他测试的影响。优点:提供清理操作,确保测试环境的整洁和可重复性…...

MySQL数据库基础(十三):关系型数据库三范式介绍
文章目录 关系型数据库三范式介绍 一、什么是三范式 二、数据冗余 三、范式的划分 四、一范式 五、二范式 六、三范式 七、总结 关系型数据库三范式介绍 一、什么是三范式 设计关系数据库时,遵从不同的规范要求,设计出合理的关系型数据库&…...

掌控互联网脉络:深入解析边界网关协议(BGP)的力量与挑战
BGP简介 边界网关协议(Border Gateway Protocol,BGP)是互联网上最重要的路由协议之一,负责在不同自治系统(AS)之间传播路由信息。BGP使得互联网中的不同网络可以互相通信,支持互联网的规模化扩…...

Vue2页面转化为Vue3
vue2element-ui转化为Vue3element plus 后台管理系统:增删查改 vue2页面: <template><div class"app-container"><div><el-form:model"queryParams"ref"queryForm"size"small":inline&qu…...

【课程作业】提取图中苹果的面积、周长和最小外接矩形的python、matlab和c++代码
提取图中苹果的面积、周长和最小外接矩形 在图像处理中,提取对象的关键属性是常见的任务之一。本文将演示如何使用三种流行的编程语言——Python、Matlab和C,利用相应的图像处理库(OpenCV或Matlab内置函数)来提取图像中苹果的面积…...

解决easyExcel模板填充时转义字符\{xxx\}失效
正常我们在使用easyExcel进行模板填充时,定义的变量会填充好对应的实际数据,未定义的变量会被清空,但是如果这个未定义的变量其实是模板的一部分,那么清空了就出错了。 在这张图里,上面的是模板填充后导出的文件&…...

在项目中使用CancelToken选择性取消Axios请求
Axios 提供了 CancelToken 类来创建取消标记。取消标记实际上是一个包含 token 标记和 cancel 方法的对象。 1、基本使用方法 const CancelToken axios.CancelToken; const source CancelToken.source();axios.get(/user/12345, {cancelToken: source.token }).catch(functi…...

[c++] 记录一次引用使用不当导致的 bug
在工作中看到了如下代码,代码基于 std::thread 封装了一个 Thread 类。Thread 封装了业务开发中常用的接口,比如设置调度策略,设置优先级,设置线程名。如下代码删去了不必要的代码,只保留能说明问题的代码。从代码实现…...

能不能节约百分之九十的算力来训练模型
Sora是由OpenAI开发的视频生成模型,它采用了多种先进的技术和架构,能够根据文本描述生成长达一分钟的高清视频。虽然OpenAI并未公开Sora的详细模型架构和实现细节,但我们可以根据公开的信息和参考论文来了解其技术架构。 Sora的核心技术架构主…...

LeetCode206: 反转链表.
题目描述 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 解题方法 假设链表为 1→2→3→∅,我们想要把它改成∅←1←2←3。在遍历链表时,将当前节点的 next指针改为指向前一个节点。由于节点没有引用其前一…...

高级统计方法 第1次作业
概念 1. 请解释什么是P值,怎么计算p值,p值结果怎么理解,p值有哪些应用......? (a)什么是P值 P值是一种用来判定假设检验结果的一个参数,它描述了在原假设为真的情况下,比所得到的…...

spinalhdl,vivado,fpga
https://spinalhdl.github.io/SpinalDoc-RTD/master spinal hdl sudo apt install openjdk-17-jdk scala curl echo “deb https://repo.scala-sbt.org/scalasbt/debian all main” | sudo tee /etc/apt/sources.list.d/sbt.list echo “deb https://repo.scala-sbt.org/scal…...

Tomcat线程池原理(下篇:工作原理)
文章目录 前言正文一、执行线程的基本流程1.1 JUC中的线程池执行线程1.2 Tomcat 中线程池执行线程 二、被改造的阻塞队列2.1 TaskQueue的 offer(...)2.2 TaskQueue的 force(...) 三、总结 前言 Tomcat 线程池,是依据 JUC 中的线程池 ThreadPoolExecutor 重新自定义…...

【服务器数据恢复】通过reed-solomon算法恢复raid6数据的案例
服务器数据恢复环境: 一台网站服务器中有一组由6块磁盘组建的RAID6磁盘阵列,操作系统层面运行MySQL数据库和存放一些其他类型文件。 服务器故障: 该服务器在工作过程中,raid6磁盘阵列中有两块磁盘先后离线,不知道是管理…...

LeetCode 2583.二叉树中的第 K 大层和:层序遍历 + 排序
【LetMeFly】2583.二叉树中的第 K 大层和:层序遍历 排序 力扣题目链接:https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/ 给你一棵二叉树的根节点 root 和一个正整数 k 。 树中的 层和 是指 同一层 上节点值的总和。 返回树中第 k …...

element ui 安装 简易过程 已解决
我之所以将Element归类为Vue.js,其主要原因是Element是(饿了么团队)基于MVVM框架Vue开源出来的一套前端ui组件。我最爱的就是它的布局容器!!! 下面进入正题: 1、Element的安装 首先你需要创建…...

websoket
WebSockets 是一种先进的技术。它可以在用户的浏览器和服务器之间打开交互式通信会话。你可以向服务器发送消息并接收事件驱动的响应,而无需通过轮询服务器的方式以获得响应,比较典型的应用场景就是即时通讯(聊天)系统。 <!DOC…...

案例:微服务从Java/SpringBoot迁移到Golan
基于 Java 的微服务,特别是那些使用 Spring Boot 的微服务,长期以来因其强大的功能和广泛的社区支持而闻名。Spring Boot 的约定优于配置方法简化了微服务的部署和开发,提供了大量开箱即用的功能,例如自动配置、独立功能和简单的依…...

小波变换模拟
小波变换是一种信号处理技术,通过在时间-频率域中使用基于小波的函数进行信号分析。小波变换在处理非平稳信号和图像时特别有用,可以将信号分解为不同频率的成分。它在数据压缩、去噪、特征提取等领域有广泛应用。 MATLAB中提供了用于二维离散小波变换的…...

cv::Mat图像操作
图像读写 //include header #include <opencv2/imgcodecs.hpp>/** Currently, the following file formats are supported: Windows bitmaps - *.bmp, *.dib (always supported) JPEG files - *.jpeg, *.jpg, *.jpe (see the Note section) JPEG 2000 files - *.jp2 (s…...

【机器学习基础】一元线性回归(适合初学者的保姆级文章)
🚀个人主页:为梦而生~ 关注我一起学习吧! 💡专栏:机器学习 欢迎订阅!后面的内容会越来越有意思~ 💡往期推荐: 【机器学习基础】机器学习入门(1) 【机器学习基…...

2024年软件测试岗位-面试
第一部分: 1、自我介绍:简历写到的快速描述,学校、学历、工作经验等(注意:不要过度优化简历,你不写别人可能会问,但你写了别人一定会问!) 第二部分: 1、功能测…...

【坑】Spring Boot整合MyBatis,一级缓存失效
一、Spring Boot整合MyBatis,一级缓存失效 1.1、概述 MyBatis一级缓存的作用域是同一个SqlSession,在同一个SqlSession中执行两次相同的查询,第一次执行完毕后,Mybatis会将查询到的数据缓存起来(缓存到内存中…...

J7 - 对于ResNeXt-50算法的思考
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制 J6周有一段代码如下 思考过程 首先看到这个问题的描述,想到的是可能使用了向量操作的广播机制然后就想想办法验证一下&…...

R3F(React Three Fiber)基础篇
之前一直在做ThreeJS方向,整理了两篇R3F(React Three Fiber)的文档,这是基础篇,如果您的业务场景需要使用R3F,您又对R3F不太了解,或者不想使用R3F全英文文档,您可以参考一下这篇&…...

torch\tensorflow在大语言模型LLM中的作用
文章目录 torch\tensorflow在大语言模型LLM中的作用 torch\tensorflow在大语言模型LLM中的作用 在大型语言模型(LLM)中,PyTorch和TensorFlow这两个深度学习框架起着至关重要的作用。它们为构建、训练和部署LLM提供了必要的工具和基础设施。 …...

设计模式-创建型模式-单例模式
0 引言 创建型模式(Creational Pattern)关注对象的创建过程,是一类最常用的设计模式,每个创建型模式都通过采用不同的解决方案来回答3个问题:创建什么(What),由谁创建(W…...

备战蓝桥杯—— 双指针技巧巧答链表1
对于单链表相关的问题,双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决: 合并两个有序链表: 使用两个指针分别指向两个链表的头部,逐一比较节点的值,将较小的节点链接到结果链表…...