leetcode做题笔记126. 单词接龙 II
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化,一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列,并满足:
- 每对相邻的单词之间仅有单个字母不同。
- 转换过程中的每个单词
si(1 <= i <= k)必须是字典wordList中的单词。注意,beginWord不必是字典wordList中的单词。 sk == endWord
给你两个单词 beginWord 和 endWord ,以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ,如果不存在这样的转换序列,返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
思路一:BFS
char** list;
int** back;
int* backSize;void dfs(char*** res, int* rSize, int** rCsize, int* ans, int last, int retLevel){int i = ans[last];if(i == 0){res[*rSize] = (char**)malloc(sizeof(char*) * retLevel);(*rCsize)[*rSize] = retLevel;for(int j = 0; j < retLevel; j++){res[*rSize][j] = list[ans[j]];}(*rSize)++;}if(last == 0){return;}for(int j = 0; j < backSize[i]; j++){int k = back[i][j];ans[last-1] = k;dfs(res,rSize,rCsize,ans,last-1,retLevel);}
}char *** findLadders(char * beginWord, char * endWord, char ** wordList, int wordListSize, int* returnSize, int** returnColumnSizes){*returnSize = 0;int size = wordListSize+1;int wlen = strlen(beginWord);list = (char**)malloc(sizeof(char*)*size); back = (int**)malloc(sizeof(int*) * size); backSize = (int*)malloc(sizeof(int) * size);int* visited = (int*)malloc(sizeof(int) * size); int** diff = (int**)malloc(sizeof(int*) * size); int* diffSize = (int*)malloc(sizeof(int) * size);int endidx = 0;for (int i = 0; i < size; ++i) {list[i] = i == 0 ? beginWord : wordList[i - 1];visited[i] = 0;diff[i] = (int*)malloc(sizeof(int) * size);diffSize[i] = 0;back[i] = (int*)malloc(sizeof(int) * size);backSize[i] = 0;if (strcmp(endWord, list[i]) == 0) {endidx = i;}}if (endidx == 0) return 0; // endword is not in the list// collect diff datafor (int i = 0; i < size; ++i) {for (int j = i; j < size; ++j) {int tmp = 0; // tmp is the difference between word[i] & word[j]for (int k = 0; k < wlen; ++k) {tmp += list[i][k] != list[j][k];if (tmp > 1) break;}if (tmp == 1) {diff[i][diffSize[i]++] = j;diff[j][diffSize[j]++] = i;}}}// BFSint* curr = (int*)malloc(sizeof(int) * size); int* prev = (int*)malloc(sizeof(int) * size); int prevSize, currSize = 1;int* currvisited = (int*)malloc(sizeof(int) * size);int level = 1; curr[0] = 0;visited[0] = 1;int retlevel = 0; while (retlevel == 0 && currSize > 0) {++level;int* tmp = prev;prev = curr;curr = tmp;prevSize = currSize;currSize = 0;for (int i = 0; i < size; ++i) {currvisited[i] = 0;}for (int i = 0; i < prevSize; ++i) {for (int j = 0; j < diffSize[prev[i]]; ++j) {int k = diff[prev[i]][j]; if (visited[k]) continue;back[k][backSize[k]++] = prev[i]; if (k == endidx) retlevel = level; if (currvisited[k]) continue; curr[currSize++] = k;currvisited[k] = 1;}}for (int i = 0; i < currSize; ++i) {visited[curr[i]] = 1;}}if (retlevel == 0) return 0; char*** res = (char***)malloc(sizeof(char**) * size);int* ans = (int*)malloc(sizeof(int) * retlevel);*returnColumnSizes = (int*)malloc(sizeof(int) * size);ans[retlevel - 1] = endidx;dfs(res, returnSize, returnColumnSizes, ans, retlevel - 1, retlevel);return res;
}
分析:
本题采用广度优先搜索将每个字符串能转换的所有序列找出,再判断是否存在最短转换序列,最后输出答案
总结:
本题考察广度优先搜索的应用,判断当前字符是否匹配,得到转换序列即可做出
相关文章:
leetcode做题笔记126. 单词接龙 II
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化,一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列,并满足: 每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 s…...
windows下运行springboot的jar包,修改替换class文件,修改配置文件application,打包
在windows下跑springboot的jar包,经常会用到一些命令行和操作。 1、修改配置文件(以application.yml为例) #提取文件 jar xvf mqtt-10.1.0.jar BOOT-INF/classes/application.yml#将文件装回jar包 jar uvf mqtt-10.1.0.jar BOOT-INF/classe…...
PMD 检查java代码:可以去掉无用的括号(UselessParentheses)
这个规则的优先级比较低。 https://docs.pmd-code.org/pmd-doc-6.55.0/pmd_rules_java_codestyle.html#uselessparentheses 无用的括号可以去掉。当然,有时候为了避免理解起来困难,加上括号反而更加清晰。 例如: public static short calc…...
【数据结构练习】栈的面试题集锦
目录 前言: 1.进栈过程中可以出栈的选择题 2.将递归转化为循环 3.逆波兰表达式求值 4.有效的括号 5. 栈的压入、弹出序列 6. 最小栈 前言: 数据结构想要学的好,刷题少不了,我们不仅要多刷题,还要刷好题&#x…...
简单工厂模式概述和使用
目录 一、简单工厂模式简介1. 定义2. 使用动机 二、简单工厂模式结构1.模式结构2. 时序图 三、简单工厂的使用实例四、简单工厂模式优缺点五、简单工厂模式在Java中的应用 一、简单工厂模式简介 原文链接 1. 定义 简单工厂模式(Simple Factory Pattern):又称为静…...
软件工程概述
软件工程概述 软件工程指的是应用计算机科学、数学及管理科学等原理,以工程化的原则和方法来解决软件问题的工程,目的是提高软件生产效率、提高软件质量、降低软件成本。 1. 计算机软件 计算机软件指的是计算机系统中的程序及其文档。程序是计算任务的…...
国际网页短信软件平台搭建定制接口说明|移讯云短信系统
国际网页短信软件平台搭建定制接口说明|移讯云短信系统 通道路由功能介绍 支持地区通道分流,支持关键字,关键词通道分流,支持白名单独立通道,支持全网通道分流,支持通道可发地区设置,通道路由分组&#x…...
Java“牵手”阿里巴巴店铺所有商品API接口数据,通过店铺ID获取整店商品详情数据,阿里巴巴店铺所有商品API申请指南
阿里巴巴平台店铺所有商品数据接口是开放平台提供的一种API接口,通过调用API接口,开发者可以获取阿里巴巴整店的商品的标题、价格、库存、月销量、总销量、库存、详情描述、图片、价格信息等详细信息 。 获取店铺所有商品接口API是一种用于获取电商平台…...
【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值
【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值 【1】问题描述【2】Oracle内置函数解决【3】mysql的内置函数INSTR()【4】mysql的内置函数FIND_IN_SET() 【1】问题描述 数据库中【库信息db】和【集群信息cluster】是一对多的关系&…...
docker基本命令记录
Docker 是一个开源的容器技术,它允许开发人员将应用程序及其所有依赖项打包到一个容器中,然后轻松地在任何地方部署和运行。以下是 Docker 的一些基本操作: 基础操作: 启动 Docker:service docker start停止 Docker:service docker stop查看 Docker 信息:docker info容器操作…...
web之利用延迟实现复杂动画、animation
文章目录 效果图htmlstyleJavaScript 效果图 html <div class"container"><div class"ball"></div><input type"range" min"0" max"1" step"0.01" /> </div>style body {display…...
TCP 和 UDP 的区别、TCP 是如何保证可靠传输的?
先来介绍一些osi七层模型 分为应用层、表示层、会话层、运输层、网络层、链路层、物理层。 应用层(数据):确定进程之间通信的性质以及满足用户需要以及提供网络和用户应用,为应用程序提供服务,DNS,HTTP,HTTPS…...
鼠标悬停阴影的效果被旁边div挡住的解决办法
出现的问题 需求要求鼠标悬停某个图片上有阴影效果,但阴影被旁边相邻的div挡住了,如图所示 解决方案 给悬停的这块div增加2个css属性 $(this).css(position, relative); $(this).css(z-index, 200);新的效果如图所示 一直写后端,前端的…...
Go用两个协程交替打印100以内的奇偶数
方式1(使用无缓冲的channel) package mainimport ( "fmt" "time")var flagChan make(chan int)func wokr1() { for i : 1; i < 100; i { flagChan <- 666 // 塞入 if i%2 1 { fmt.Println("协程1打印:", i) …...
css 文字单行多行超出长度后显示 ...
0.超出… 1、单行文本超出 <div class"content">测试数据:css单行文本超出显示省略号--------</div><style> .content{width: 200px;height: 200px;overflow:hidden;white-space: nowrap;text-overflow: ellipsis;-o-text-overflow:el…...
C++将派生类赋值给基类
在 C/C++ 中经常会发生数据类型的转换,例如将 int 类型的数据赋值给 float 类型的变量时,编译器会先把 int 类型的数据转换为 float 类型再赋值;反过来,float 类型的数据在经过类型转换后也可以赋值给 int 类型的变量。 数据类型转换的前提是,编译器知道如何对数据进行取舍…...
海外问卷调查是做什么的?
大家好,我是橙河。现在我来给大家简单讲解一下海外问卷调查是做什么的? 多年以前,人们就开始在网上进行海外问卷调查了。最常见的方法是通过问卷网站、做问卷或者论坛进行调查,现在则更多地使用各种渠道进行调查。海外国家对于问…...
Redis——数据结构介绍
Redis是一个key-value的数据库,key一般是String类型,不过value的类型是多样的: String:hello wordHash:{name:"Jack",age:21}List:[A -> B -> C -> D]Set:{A,B,C}SortedSet…...
附录2-将三国演义按章节存储为不同的txt(bs4)
地址 《三国演义》全集在线阅读_史书典籍_诗词名句网 目录 1 项目分析 2 代码 1 项目分析 我们可以在首页中找到所有的章节 每一个章节是一个a标签,a标签连接到该章节的内容 但这个网站他有bug,章节都是乱套的,我们无视这种错误&#…...
现代C++中的从头开始深度学习:【6/8】成本函数
现代C中的从头开始深度学习:成本函数 一、说明 在机器学习中,我们通常将问题建模为函数。因此,我们的大部分工作都包括寻找使用已知模型近似函数的方法。在这种情况下,成本函数起着核心作用。 这个故事是我们之前关于卷积的讨论的…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
