leetcode127单词接龙刷题打卡
127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk:
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时,每个si都在wordList中。注意,beginWord不需要在wordList中。 sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。
示例 1:
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出:5
解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2:
输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出:0
解释:endWord "cog" 不在字典中,所以无法进行转换。
提示:
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有字符串 互不相同
题解思路
在学习图论的时候做的一道题,完全没有思路,之前做的题都是二维矩阵,有个图样,轮到每个点有四个方向供我选择,这道题只有一个单词列表。
待解决问题:
-
深搜or广搜
-
如何建图
广搜
这道题应该用广度搜索,题目中要求最短路径,用广搜的话如果遍历到了则就是那么对应的路径就是最短路径
关于建图
之前是有一个图,然后我们遍历到每一个点后尝试该点的四个方向,
这道题没有图我们遍历到一个单词后该如何尝试方向呢?
题目要求每次只改变一个单词的一个字母且改变后的单词需要出现在wordlist中,我们就可以基于改变一个字母来确定遍历的方向
遍历方向为:
到每一个单词时,有word_length*26个方向供我们遍历
while(!que.empty()){string word = que.front(); que.pop();int path = visited[word]; // unordered_mapfor(int i = 0; i < word.size(); i++){string newWord = word;for(int j = 0; j < 26; j++){newWord[i] = j + 'a';// 入队处理 and 终止条件处理}}
}
我们对比一些二维矩阵的广搜核心框架
while(!que.empty()){pair<int, int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for(int i = 0; i < 4; i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];// 入队处理 and 终止条件处理}
}
通过广搜框架我们不需要显示的建图就可以像图一样搜索。
完整代码
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end());if(wordSet.find(endWord) == wordSet.end()) return 0;unordered_map<string, int> visited;visited[beginWord] = 1;queue<string> que;que.push(beginWord);while(!que.empty()){string word = que.front(); que.pop();int path = visited[word];for(int i = 0; i < word.size(); i++){string newWord = word;for(int j = 0; j < 26; j++){newWord[i] = j + 'a';if(newWord == endWord) return path + 1;if(wordSet.find(newWord) != wordSet.end() && visited.find(newWord) == visited.end()){visited[newWord] = path + 1;que.push(newWord);}}}}return 0;}
};
相关文章:
leetcode127单词接龙刷题打卡
127. 单词接龙 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk: 每一对相邻的单词只差一个字母。对于 1 < i < k 时,每个 si 都在 wordList 中。注意&am…...
基于SSM的物流管理系统
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...
EagleSDR USB HAT FT600
给EagleSDR做了个USB 3.0的子卡,采用FT600方案,实物如下: 用FT600DataStreamerDemoApp测试,速度如下: 由于FT600是16bit的接口,如果用FT601的32bit接口,性能应该还会有大幅提升。 测试代码很简…...
Java多线程(四)锁策略(CAS,死锁)和多线程对集合类的使用
锁策略(CAS,死锁)和多线程对集合类的使用 锁策略 1.乐观锁VS悲观锁 2.轻量级锁VS重量级锁 3.自旋锁VS挂起等待锁 4.互斥锁VS读写锁 5.可重入锁vs不可重入锁 死锁的第一种情况 死锁的第二种情况 死锁的第三种情况 CAS 1.实现原子类 …...
基于spring boot+ vue+ mysql开发的UWB室内外定位系统源码
现代制造业厂区面积大、人员数量多、物资设备不断增加,随着工业信息化技术的发展,大型制造企业中对人员、车辆、物资的管理要求越来越细致。 高精度定位管理系统使用UWB室内定位技术,通过在厂区安装定位基站,为人员或设备佩戴定位…...
第2章_瑞萨MCU零基础入门系列教程之面向过程与面向对象
本教程基于韦东山百问网出的 DShanMCU-RA6M5开发板 进行编写,需要的同学可以在这里获取: https://item.taobao.com/item.htm?id728461040949 配套资料获取:https://renesas-docs.100ask.net 瑞萨MCU零基础入门系列教程汇总: ht…...
数字图像处理:亮度对比度-几何变换-噪声处理
文章目录 数字图像增强亮度与对比度转换几何变换图像裁剪尺寸变换图像旋转 噪声处理添加噪声处理噪声 数字图像增强 亮度与对比度转换 图像变换可分为以下两种: 点算子:基于像素变换,在这一类图像变换中,仅仅根据输入像素值计算…...
maven报错:[ERROR] 不再支持源选项 7。请使用 8 或更高版本。
解决方案 pom.xml文件中增加maven编译的java.version jdk版本设置,以及maven.compiler.source 资源编译jdk版本设置和maven.compiler.target 资源构建jdk版本设置 JDK:6~8 一般都是1.6,1.7,1.8的写法。 <properties><…...
MySQL基础3-约束
MySQL基础3-约束 一. 约束概述1.1 概念1.2 目的1.3 分类 二. 约束演示三. 外键约束3.1 概念3.2 语法三. 删除/更新行为 一. 约束概述 1.1 概念 约束是作用于表中字段上的规则,用于限制存储在表中的数据 1.2 目的 保证数据库中数据的正确、有效性和完整…...
OJ练习第166题——课程表(拓扑排序问题)
课程表 力扣链接:207. 课程表 题目描述 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] [ai, bi] ,表…...
单臂路由实现VLAN间路由
单臂路由实现VLAN间路由 单臂路由 概述拓扑图PC配置LSW2 接入层交换机LSW3 接入层交换机LSW1 汇聚层交换机R1 路由器ping 测试 单臂路由 概述 单臂路由的原理是通过一台路由器,使 VLAN 间互通数据通过路由器进行三层转发。 如果在路由器上为每个 VLAN 分配一个单独…...
【VSCode】文件模板创建及使用.md
背景 最近使用VSCode学习Vue项目比较频繁,每次创建Vue文件都要手动写重复代码,特别麻烦,就上网查找自动生成代码的说明,结果发现VSCode有代码模板,怪怪,感觉发现新大陆了(low!)。 配置 打开配置 方式一&a…...
【漏洞复现】EnjoySCM存在文件上传漏洞
漏洞描述 EnjoySCM是一款适应于零售企业的供应链管理软件,主要为零售企业的供应商提供服务。EnjoySCM的目的是通过信息技术,实现供应商和零售企业的快速、高效、准确的信息沟通、管理信息交流。。 该系统存在任意文件上传漏洞,攻击者通过漏洞可以获取服务器的敏感信息。 …...
MaPLe: Multi-modal Prompt Learning
本文也是LLM系统的文章,主要是面向多模态的大语言模型,针对《MaPLe: Multi-modal Prompt Learning》的翻译。 MaPLe:多模态提示学习 摘要1 引言2 相关工作3 方法4 实验5 结论 摘要 CLIP等预先训练的视觉语言(V-L)模型…...
软件测试/测试开发丨Jenkins Pipeline 学习笔记
点此获取更多相关资料 本文为霍格沃兹测试开发学社学员学习笔记分享 原文链接:https://ceshiren.com/t/topic/26711 1. Jenkins节点 1.1 常用的节点 内建节点SSH节点Java Web节点 1.1.1 SSH节点配置 远程工作目录 节点中必须有该目录,用于下载和运行j…...
java多线程——线程池
线程池 线程池创建线程池关闭线程池使用获取多个结果 线程池 一个线程池中存在许多准备运行的空闲线程,把Runnable对象交给线程池,会有一个线程调用其run()方法,当调用完后线程不会死亡,而是在池中继续为下一次请求服务 利用线程…...
Linux文件操作
目录 复制文件、目录 cp 移动 重命名文件或目录 mv 创建删除文件 touch rm(remove) 创建删除目录 mkdir(make directory) rmdir(remove directory) 复制文件、目录 cp cp(copy) 同一个目录下复制,所以重命名了一下;把它复制到linuxcast.net/目录下可以…...
Tomcat多实例 + Tomcat负载均衡、动静分离(Nginx联动)
多实例联动 一、Tomcat 多实例1.1 什么是Tomcat多实例?1.2 配置思路1.3 配置实现1.3.1 安装jdk1.3.2 安装tomcat1.3.3 配置 tomcat 环境变量1.3.4 修改端口号1.3.5 修改各 tomcat 实例中的 startup.sh 和 shutdown.sh 文件,添加 tomcat 环境变量1.3.6 启…...
bootstrap和application的区别
SpringBoot项目的配置文件支持两种四个: bootstrap和application。 YML文件两个:bootstrap.yml,application.yml 属性文件两个:bootstrap.properties,application.properties 配置文件优先级 SpringBoot支持同时使用…...
【狂神】SpringMVC笔记(一)之详细版
1.Restful 风格 概念: 实现方式: 使用PathVariable 在url相同的情况下,会根据请求方式的不同来执行不同的方法。 使用RestFull风格的好处:简洁、高效、安全 2、接受请求参数及数据回显 2.1、请求参数 方式一:这里…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
