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

127. 单词接龙

和433.最小基因变化这道题一样的解法。
https://blog.csdn.net/qq_43606119/article/details/135538247

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> cnt = new HashSet<>();for (int i = 0; i < wordList.size(); ++i) {cnt.add(wordList.get(i));}if (!cnt.contains(endWord)) return 0;Set<String> visited = new HashSet<>();Queue<String> q = new ArrayDeque<>();q.offer(beginWord);visited.add(beginWord);int step = 1;while (!q.isEmpty()) {int size = q.size();for (int i = 0; i < size; ++i) {String curr = q.poll();for (int u = 0; u < curr.length(); ++u) {for (int v = 0; v < 26; ++v) {if (curr.charAt(u) != 'a' + v) {StringBuffer sb = new StringBuffer(curr);sb.setCharAt(u, (char)('a' + v));String next = sb.toString();if (!visited.contains(next) && cnt.contains(next)) {if (next.equals(endWord)) return step + 1;q.offer(next);visited.add(next);}}}}}++step;}return 0;}
}

改进:

在本题中可以使用虚拟节点将各个单词进行连接,例如hit可以有三个虚拟节点hi*、h*t、*it,将其和hit进行连接,所有单词都如此处理,优化建图。

注意因为添加了虚拟节点,所以我们得到的距离为实际最短路径长度的两倍。同时我们并未计算起点对答案的贡献,所以我们应当返回距离的一半再加一的结果。

class Solution {Map<String, Integer> wordID = new HashMap<>();List<List<Integer>> edge = new ArrayList<>();int nodeNum = 0;public int ladderLength(String beginWord, String endWord, List<String> wordList) {for (String word : wordList) {addEdge(word);}addEdge(beginWord);if (!wordID.containsKey(endWord)) {return 0;}// 初始化dis数组,表示从beginWord到每个单词的最短转变路径长度,初始值为Integer.MAX_VALUE。int[] dis = new int[nodeNum];Arrays.fill(dis, Integer.MAX_VALUE);int beginID = wordID.get(beginWord), endID = wordID.get(endWord);dis[beginID] = 0;Queue<Integer> q = new LinkedList<>();q.offer(beginID);while (!q.isEmpty()) {int curr = q.poll();if (curr == endID) return dis[curr] / 2 + 1;for (int e : edge.get(curr)) {if (dis[e] == Integer.MAX_VALUE) {dis[e] = dis[curr] + 1;q.offer(e);}}}return 0;}private void addEdge(String word) {addWord(word);int id1 = wordID.get(word);char[] array = word.toCharArray();for (int i = 0; i < array.length; ++i) {char temp = array[i];array[i] = '*';String newWord = new String(array);addWord(newWord);int id2 = wordID.get(newWord);edge.get(id1).add(id2);edge.get(id2).add(id1);array[i] = temp;}}private void addWord(String word) {if (!wordID.containsKey(word)) {wordID.put(word, nodeNum++);edge.add(new ArrayList<Integer>());}}
}

相关文章:

127. 单词接龙

和433.最小基因变化这道题一样的解法。 https://blog.csdn.net/qq_43606119/article/details/135538247 class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> cnt new HashSet<>();for (int …...

计算机算法贪心算法

贪心算法&#xff08;Greedy Algorithm&#xff09;是一种常见的算法思想&#xff0c;它在每一步选择当前状态下最优的解决方案&#xff0c;从而希望最终能够达到全局最优解。 贪心算法的基本思路是每一步都选择当前状态下的局部最优解&#xff0c;而忽略了当前选择所带来的影…...

基于css实现动画效果

介绍 本文将会基于css&#xff0c;实现各种动画效果&#xff0c;接下来会从简单几个例子入手。 案例 三颗球 <!DOCTYPE html> <html lang"en"><head><meta charset"utf-8" /><title>React App</title><style>…...

18.将文件上传至云服务器 + 优化网站的性能

目录 1.将文件上传至云服务器 1.1 处理上传头像逻辑 1.1.1 客户端上传 1.1.2 服务器直传 2.优化网站的性能 2.1 本地缓存优化查询方法 2.2 压力测试 1.将文件上传至云服务器 客户端上传&#xff1a;客户端将数据提交给云服务器&#xff0c;并等待其响应&#xff1b;用户…...

Linux: module: kheaders;CONFIG_IKHEADERS

文章目录 参考错误开一个玩笑。configcommit参考 https://github.com/iovisor/bcc/pull/2312 https://github.com/iovisor/bcc/pull/3588 https://bugs.gentoo.org/809347 https://lore.kernel.org/lkml/20190408212855.233198-1-joel@joelfernandes.org/ 错误 <built-in…...

Page 251~254 Win32 GUI项目

win32_gui 源代码&#xff1a; #if defined(UNICODE) && !defined(_UNICODE)#define _UNICODE #elif defined(_UNICODE) && !defined(UNICODE)#define UNICODE #endif#include <tchar.h> #include <windows.h>/* Declare Windows procedure */…...

Kafka(七)可靠性

目录 1 可靠的数据传递1.1 Kafka的可靠性保证1.2 复制1.3 Broker配置1.3.1 复制系数1.3.2 broker的位置分布1.3.3 不彻底的首领选举1.3.4 最少同步副本1.3.5 保持副本同步1.3.6 持久化到磁盘flush.messages9223372036854775807flush.ms9223372036854775807 1.2 在可靠的系统中使…...

Spring Data JPA入门到放弃

参考文档&#xff1a;SpringData JPA&#xff1a;一文带你搞懂 - 知乎 (zhihu.com) 一、 前言 1.1 概述 Java持久化技术是Java开发中的重要组成部分&#xff0c;它主要用于将对象数据持久化到数据库中&#xff0c;以及从数据库中查询和恢复对象数据。在Java持久化技术领域&a…...

MES系统数据采集的几种方式

生产制造执行MES系统具有能够帮助企业实现生产数据收集与分析、生产计划管理、生产过程监控等的功能板块&#xff0c;在这里小编就不一一介绍了&#xff0c;主要讲讲它的数据采集功能板块&#xff0c;可以说&#xff0c;数据采集是该系统进行数据统计与生产管理等后续工作的基础…...

铭文 LaunchPad 平台 Solmash 推出早鸟激励计划

为感谢用户对Solmash的支持&#xff0c;Solmash 特别推出“Solmash早鸟激励计划”&#xff0c;以回馈社区的早期参与者&#xff0c;这是专为已经参与Staking Pool或Honest Pool的用户推出的激励。 Solmash NFT激励 被列入早鸟计划的用户&#xff0c;可通过点击&#xff1a;sol…...

【前端规范】

1 前言 HTML 作为描述网页结构的超文本标记语言&#xff0c;一直有着广泛的应用。本文档的目标是使 HTML 代码风格保持一致&#xff0c;容易被理解和被维护。 2 代码风格 2.1 缩进与换行 [强制] 使用 4 个空格做为一个缩进层级&#xff0c;不允许使用 2 个空格 或 tab 字符…...

12、JVM高频面试题

1、JVM的主要组成部分有哪些 JVM主要分为下面几部分 类加载器&#xff1a;负责将字节码文件加载到内存中 运行时数据区&#xff1a;用于保存java程序运行过程中需要用到的数据和相关信息 执行引擎&#xff1a;字节码文件并不能直接交给底层操作系统去执行&#xff0c;因此需要…...

【Docker】Docker安装入门教程及基本使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《Docker实战》。&#x1f3af;&#x1f3af; &…...

语义解析:如何基于SQL去实现自然语言与机器智能连接的桥梁

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 &#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 语义解析 定义 作用 语义解析的应用场景 场景一&#xff1a; 场景二&#xff1a; 总结语…...

Java项目:117SpringBoot动漫论坛网站

博主主页&#xff1a;Java旅途 简介&#xff1a;分享计算机知识、学习路线、系统源码及教程 文末获取源码 117SpringBoot动漫论坛网站 一、项目介绍 动漫论坛网站是由SpringBootMybatis开发的&#xff0c;旅游网站分为前台和后台&#xff0c;前台为用户浏览&#xff0c;后台进…...

Jenkins基础篇--添加节点

节点介绍 Jenkins 拥有分布式构建(在 Jenkins 的配置中叫做节点)&#xff0c;分布式构建能够让同一套代码在不同的环境(如&#xff1a;Windows 和 Linux 系统)中编译、测试等。 Jenkins 运行的主机在逻辑上是 master 节点&#xff0c;下图是主节点和从节点的关系。 添加节点 …...

【C++】手撕 list类(包含迭代器)

目录 1&#xff0c;list的介绍及使用 2&#xff0c;list_node 3&#xff0c;list_node() 3&#xff0c;list 4&#xff0c;list() 5&#xff0c;push_back(const T& x) 6&#xff0c;print() 7&#xff0c;_list_iterator 8&#xff0c;operator*() 9&#xff0c…...

@Autowired 和 @Resource 的区别是什么?

Java面试题目录 Autowired 和 Resource 的区别是什么&#xff1f; Autowired 是 Spring 提供的注解。默认的注入方式为byType&#xff08;根据类型进行匹配&#xff09;。 Resource 是 JDK 提供的注解。默认注入方式为 byName&#xff08;根据名称进行匹配&#xff09;。 当一…...

栈和排序.

给你一个1->n的排列和一个栈&#xff0c;入栈顺序给定 你要在不打乱入栈顺序的情况下&#xff0c;对数组进行从大到小排序 当无法完全排序时&#xff0c;请输出字典序最大的出栈序列 输入 第一行一个数n 第二行n个数&#xff0c;表示入栈的顺序&#xff0c;用空格隔开&…...

springboot 多数据源怎么配置在控制台的sql打印日志

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...