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

leetcode 127. 单词接龙

题目:127. 单词接龙 - 力扣(LeetCode)

先建立一颗trie树,从beginWord开始bfs;bfs的过程中,对trie树进行dfs寻找“只差一个字母”的其他未遍历到的字符串;直到bfs遍历到endWord。

struct Node {Node** c;string str;bool v = false;Node() {c = (Node**) malloc(26 * sizeof(Node*));memset(c, 0, 26 * sizeof(Node*));}
};
class Solution {
public:void dfs(list<string>& bfs, list<int>& val, const string& s, int path, Node* node, int idx, bool changed) {char c = s[idx] - 'a';Node* t;if (idx == s.length() - 1) {if (changed) {t = node->c[c];if (t && !t->v) {t->v = true;bfs.push_back(t->str);val.push_back(path + 1);}} else {for (int i = 0; i < 26; i++) {if (i == c) continue;t = node->c[i];if (t && !t->v) {t->v = true;bfs.push_back(t->str);val.push_back(path + 1);}}}return;}for (int i = 0; i < 26; i++) {if (!node->c[i]) {continue;}if (i == c) {dfs(bfs, val, s, path, node->c[i], idx + 1, changed);} else if (!changed) {dfs(bfs, val, s, path, node->c[i], idx + 1, true);}}}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {Node* root = new Node;bool hasEndWord = false;char c;Node* t;string s;for (int i = 0; i < wordList.size(); i++) {s = wordList[i];if (s.compare(endWord) == 0) {hasEndWord = true;}t = root;for (int j = 0; j < s.length(); j++) {c = s[j] - 'a';if (!t->c[c]) {t->c[c] = new Node;}t = t->c[c];}t->str = s;}if (!hasEndWord) {return 0;}list<string> bfs;bfs.push_back(beginWord);list<int> val;val.push_back(1);int path;while (!bfs.empty()) {s = bfs.front();bfs.pop_front();path = val.front();val.pop_front();
//            printf("** %s %d\n", s.data(), path);if (s.compare(endWord) == 0) {return path;}dfs(bfs, val, s, path, root, 0, false);}return 0;}
};

相关文章:

leetcode 127. 单词接龙

题目&#xff1a;127. 单词接龙 - 力扣&#xff08;LeetCode&#xff09; 先建立一颗trie树&#xff0c;从beginWord开始bfs&#xff1b;bfs的过程中&#xff0c;对trie树进行dfs寻找“只差一个字母”的其他未遍历到的字符串&#xff1b;直到bfs遍历到endWord。 struct Node …...

如何开发一个支持海量分布式锁的应用库

分布式锁是一种用于控制分布式系统中资源访问的同步机制&#xff0c;确保在任意时刻只有一个客户端能够获取到锁&#xff0c;并对共享资源进行操作。 作用 1.保证数据一致性&#xff1a;在多个节点并发执行的情况下&#xff0c;分布式锁可以防止同时修改同一份数据&#xff0c…...

JavaScript系列(17)--类型系统模拟

JavaScript类型系统模拟 &#x1f3ad; 今天&#xff0c;让我们深入探讨JavaScript中的类型系统模拟。虽然JavaScript是一门动态类型语言&#xff0c;但我们可以通过各种方式来实现类型检查和验证。 类型系统基础 &#x1f31f; &#x1f4a1; 小知识&#xff1a;JavaScript是…...

openssl编译

关于windows下&#xff0c;openssl编译 环境准备 安装 perl:https://djvniu.jb51.net/200906/tools/ActivePerl5_64.rar安装nasm&#xff1a;https://www.nasm.us/pub/nasm/releasebuilds/2.13.01/win64/nasm-2.13.01-installer-x64.exe下载opensll源码&#xff1a;https://o…...

校园网络综合布线系统设计与实践

校园网络综合布线系统设计与实践 摘要&#xff1a;随着信息时代的发展&#xff0c;网络综合布线显得更加重要。综合布线技术也日益引起人的重视。综合布线管理系统是一个实用性十分强的系统工程&#xff0c;同样又是现代社区信息化建设的基础与必要产品&#xff0c;是对多用途…...

如果商品信息更新,爬虫会失效吗?

当商品信息更新时&#xff0c;爬虫是否失效取决于更新的具体内容。以下是一些可能影响爬虫的因素&#xff1a; 可能导致爬虫失效的情况 HTML结构变化&#xff1a;如果 yiwugo 平台更新了商品详情页面的 HTML 结构&#xff0c;比如改变了元素的标签、类名或 ID&#xff0c;那么…...

【UE5 C++课程系列笔记】27——多线程基础——ControlFlow插件的基本使用

目录 步骤 一、搭建基本同步框架 二、添加委托 三、添加蓝图互动框架 四、修改为异步框架 完整代码 通过一个游戏初始化流程的示例来介绍“ControlFlows”的基本使用。 步骤 一、搭建基本同步框架 1. 勾选“ControlFlows”插件 2. 新建一个空白C类&#xff0c;这里…...

有收到腾讯委托律师事务所向AppStore投诉带有【水印相机】主标题名称App的开发者吗

近期&#xff0c;有多名开发者反馈&#xff0c;收到来自腾讯科技 (深圳) 有限公司委托北京的一家**诚律师事务所卞&#xff0c;写给AppStore的投诉邮件。 邮件内容主要说的是&#xff0c;腾讯注册了【水印相机】这四个字的商标&#xff0c;所以你们这些在AppStore上的app&…...

标定 3

标定场景与对应的方式 标定板标定主要应用场景: (1)无法获取到执行机构物理坐标值,比如相机固定,执行机构为传送带等 (2)相机存在畸变等非线性标定情况,需要进行畸变校正 (3)标定单像素精度 (4)获取两个相机之间的坐标系关系 标定板操作步骤: (1)确定好拍…...

用 C# 绘制谢尔宾斯基垫片

谢尔宾斯基垫片是一个三角形&#xff0c;分解成多个小三角形&#xff0c;如右图所示。有几种方法可以生成这种垫片。这里展示的方法是其中一种比较令人惊讶的方法。 程序从三个点开始&#xff08;图中圆圈所示&#xff09;。“当前位置”从其中一个点开始。为了生成后续点&…...

java.lang.NoClassDefFoundError: javax/xml/bind/DatatypeConverter

今天在朋友机子上运行代码&#xff0c;在生成token的时候&#xff0c;遇到了这样一个问题&#xff1a; Caused by: java.lang.NoClassDefFoundError: javax/xml/bind/DatatypeConverter at io.jsonwebtoken.impl.Base64Codec.decode(Base64Codec.java:26) ~[jjwt-0.9.1.jar:0.…...

双因素身份验证技术在NPI区域邮件安全管控上的解决思路

在制造业中&#xff0c;NPI&#xff08;New Product Introduction&#xff0c;新产品导入&#xff09;区域是指专门负责新产品从概念到市场推出全过程的部门或团队。NPI 的目标是确保新产品能够高效、高质量地投入生产&#xff0c;并顺利满足市场需求。在支撑企业持续创新和竞争…...

java后端对接飞书登陆

java后端对接飞书登陆 项目要求对接第三方登陆&#xff0c;飞书登陆&#xff0c;次笔记仅针对java后端&#xff0c;在看本笔记前&#xff0c;默认已在飞书开发方已建立了应用&#xff0c;并获取到了appid和appsecret。后端要做的其实很简单&#xff0c;基本都是前端做的&…...

记录一次Android Studio的下载、安装、配置

目录 一、下载和安装 Android Studio 1、搜索下载Android studio ​2、下载成功后点击安装包进行安装&#xff1a; 3、这里不用打勾&#xff0c;直接点击安装 &#xff1a; 4、完成安装&#xff1a; 5、这里点击Cancel就可以了 6、接下来 7、点击自定义安装&#xff1a…...

直流无刷电机控制(FOC):电流模式

目录 概述 1 系统框架结构 1.1 硬件模块介绍 1.2 硬件实物图 1.3 引脚接口定义 2 代码实现 2.1 软件架构 2.2 电流检测函数 3 电流环功能实现 3.1 代码实现 3.2 测试代码实现 4 测试 概述 本文主要介绍基于DengFOC的库函数&#xff0c;实现直流无刷电机控制&#x…...

73.矩阵置零 python

矩阵置零 题目题目描述示例 1&#xff1a;示例 2&#xff1a;提示&#xff1a; 题解思路分析Python 实现代码代码解释提交结果 题目 题目描述 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例…...

垃圾收集算法

分代收集理论 分代收集理论&#xff0c;建立在两个分代假说之上。 弱分代假说&#xff1a;绝大多数对象都是朝圣夕灭的。 强分代假说&#xff1a;熬过越多次垃圾收集的过程的对象就越难以消亡。 这两个分代假说奠定了垃圾收集器的一致设计原则&#xff1a;收集器应该将Java…...

SQL-leetcode-262. 行程和用户

262. 行程和用户 表&#xff1a;Trips --------------------- | Column Name | Type | --------------------- | id | int | | client_id | int | | driver_id | int | | city_id | int | | status | enum | | request_at | varchar | --------------------- id 是这张表的主键…...

太原理工大学软件设计与体系结构 --javaEE

这个是简答题的内容 选择题的一些老师会给你们题库&#xff0c;一些注意的点我会做出文档在这个网址 项目目录预览 - TYUT复习资料:复习资料 - GitCode 希望大家可以给我一些打赏 什么是Spring的IOC和DI IOC 是一种设计思想&#xff0c;它将对象的创建和对象之间的依赖关系…...

Leetcode 139. 单词拆分 动态规划

原题链接&#xff1a;Leetcode 139. 单词拆分 递归&#xff0c;超时 class Solution { public:bool isfind(string s,map<string,int>& mp){for(auto x:mp){string wordx.first;if(sword) return true;int nword.size();if(n>s.size()) continue;string s1s.subs…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...