【数据结构-字典树】力扣14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空,则仅由小写英文字母组成
class Solution {
private:struct dt { vector<dt*> children;bool isEnd;dt() : children(26, nullptr), isEnd(false) {}};dt* root;
public:Solution() {root = new dt(); // 初始化根节点}string longestCommonPrefix(vector<string>& strs) {for(string word : strs){if(word.empty()) return "";add(word);}string res = "";dt* node = root;while(true){int count = 0;int lastChild = -1;for(int i = 0; i < 26; i++){if(node->children[i] != nullptr){count++;lastChild = i;}}if(count != 1) break;if(node->children[lastChild]->isEnd){res += (lastChild + 'a');break;}res += (lastChild + 'a');node = node->children[lastChild];}return res;}void add(string word){dt* node = root;for(char ch : word){ch -= 'a';if(node->children[ch] == nullptr){node->children[ch] = new dt();}node = node->children[ch];}node->isEnd = true;}
};
我们可以使用tried树来解决这道题,首先先将所有strs的word构造出一个字典树。接下来我们从字典树的根节点不断向下查找,我们看他有几个子节点,如果有多个子节点,就说明不需要继续添加字符了,因为只有当children的数量为1个的时候,说明是公共前缀。
然后我们还要检查我们选择的下一个节点是不是某个word的结尾,如果是的话,就将其添加到res后,停止继续查找添加。
相关文章:
【数据结构-字典树】力扣14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入:strs [“flower”,“flow”,“flight”] 输出:“fl” 示例 2: 输入:strs [“dog”,“racecar…...
《深入浅出HTTPS》读书笔记(31):HTTPS和TLS/SSL
《深入浅出HTTPS》读书笔记(31):HTTPS和TLS/SSL TLS/SSL协议和应用层协议无关,它只是加密应用层协议(比如HTTP)并传递给下层的TCP。 HTTP和TLS/SSL协议组合在一起就是HTTPS, HTTPS等…...
Go学习:Go语言中if、switch、for语句与其他编程语言中相应语句的格式区别
Go语言中的流程控制语句逻辑结构与其他编程语言类似,格式有些不同。Go语言的流程控制中,包括if、switch、for、range、goto等语句,没有while循环。 目录 1. if 语句 2. switch语句 3. for语句 4. range语句 5. goto语句(不常用…...
L30.【LeetCode笔记】设计链表
1.题目 707. 设计链表 - 力扣(LeetCode) 你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 如果是双向…...
java日志框架详解-Log4j2
一、概述 Apache Log4j 2 (Log4j – Apache Log4j 2)是对Log4j的升级,它比其前身Log4j 1.x提供了重大改进,并参考了Logback中优秀的设计,同时修复了Logback架构中的一些问题。被誉为是目前最优秀的Java日志框架&#x…...
C++中vector追加vector
在C中,如果你想将一个vector追加到另一个vector的后面,可以使用std::vector的成员函数insert或者std::copy,或者简单地使用std::vector的push_back方法逐个元素添加。这里我将展示几种常用的方法: 方法1:使用insert方…...
加一(66)
66. 加一 - 力扣(LeetCode) 解法: class Solution { public:vector<int> plusOne(vector<int>& digits) {bool plus_one true;for (int i digits.size() - 1; i > 0; --i) {if (plus_one) {int tmp digits[i] 1;if …...
远程连接-简化登录
vscode通过ssh连接远程服务器免密登录(图文)_vscode ssh-CSDN博客...
canvas的基本用法
canvas canvas元素简介 1.是个container元素<canvas width100 height100></canvas>,有开闭标签 2.有且只有width和height两个attribute,不需要写单位 canvas的基本使用 const canvasEl document.getElementById(canvas01) const ctx …...
Tailwind CSS - Tailwind CSS 引入(安装、初始化、配置、引入、构建、使用 Tailwind CSS)
一、Tailwind CSS 概述 Tailwind CSS 是一个功能优先的 CSS 框架,它提供了大量的实用类(utility classes),允许开发者通过组合这些类来快速构建用户界面 Tailwind CSS 与传统的 CSS 框架不同(例如,Bootstr…...
鸿蒙开发黑科技“stack叠层”替代customdialog
前一篇提到的问题,本篇博文提出了一个解决方案: arkui-x LongPressGesture触发customdialog踩坑记录-CSDN博客 前一段时间遇到的这个问题,通过排除法观察,锁定为customdialog组件有bug,极为容易挂死。不论如何调整使用方法,都还是会触发挂死。 反馈给arkui团队,说是在…...
FreeRTOS从入门到精通 第十五章(事件标志组)
参考教程:【正点原子】手把手教你学FreeRTOS实时系统_哔哩哔哩_bilibili 一、事件标志组简介 1、概述 (1)事件标志位是一个“位”,用来表示事件是否发生。 (2)事件标志组是一组事件标志位的集合&#x…...
智慧园区管理平台实现智能整合提升企业运营模式与管理效率
内容概要 在当今数字化的背景下,智慧园区管理平台正逐渐成为企业提升运营效率和管理模式的重要工具。这个平台汇聚了多种先进技术,旨在通过智能整合各类资源与信息,帮助企业实现全面的管理创新。 智慧园区管理平台不仅仅是一个数据处理工具…...
markdown公式特殊字符
个人学习笔记 根号 在 Markdown 中,要表示根号 3,可以使用 LaTeX 语法来实现。常见的有以下两种方式: 行内公式形式:使用一对美元符号 $ 将内容包裹起来,即 $\sqrt{3}$ ,在支持 LaTeX 语法渲染的 Markdow…...
【深度分析】微软全球裁员计划不影响印度地区,将继续增加当地就业机会
当微软的裁员刀锋掠过全球办公室时,班加罗尔的键盘声却愈发密集——这场资本迁徙背后,藏着数字殖民时代最锋利的生存法则。 表面是跨国公司的区域战略调整,实则是全球人才市场的地壳运动。微软一边在硅谷裁撤年薪20万美金的高级工程师&#x…...
学习数据结构(5)单向链表的实现
(1)头部插入 (2)尾部删除 (3)头部删除 (4)查找 (5)在指定位置之前插入节点 (6)在指定位置之后插入节点 (7)删除…...
刷题记录 HOT100回溯算法-5:22. 括号生成
题目:22. 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((()))","(()())","(())()",…...
Keepalived高可用集群企业应用实例二
一、实现ipvs的高可用性 ipvs相关配置 虚拟服务器配置结构: virtual_server ip port { …… real_server { …… } real_server { …… } } virtual server (虚拟服务器)的定义格式 virtual_server ip port 定义虚拟主机ip地址及其端口 virtual_server …...
C++计算特定随机操作后序列元素乘积的期望
有一个长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。初始序列的所有元素均为 0 0 0。再给定正整数 m m m、 c c c和 ( n − m 1 ) (n-m1) (n−m1)个正整数 b 1 , b 2 , . . . , b n − m 1 b_1,b_2,...,b_{n-m1} b1,b2,...,bn−m1…...
c++字母大小写转换
可以通过标准库中的 <algorithm> 和 <cctype> 头文件来实现大小写转换。以下是常用的方法: 1. 使用 std::transform 和 std::toupper/std::tolower 1.1 转换为大写 #include <iostream> #include <string> #include <algorithm> //…...
Llama-3.2V-11B-cot开源大模型案例:科研论文插图数据真实性初筛
Llama-3.2V-11B-cot开源大模型案例:科研论文插图数据真实性初筛 1. 项目背景与价值 科研论文插图的真实性核查是学术出版领域的重要环节。传统人工检查方式存在效率低、主观性强等问题。Llama-3.2V-11B-cot多模态大模型为解决这一问题提供了创新方案。 这款基于M…...
英雄联盟玩家的终极效率工具:League-Toolkit 完整指南
英雄联盟玩家的终极效率工具:League-Toolkit 完整指南 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power 🚀. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 还在为错过匹配确认而烦恼&a…...
5分钟终极指南:Windows虚拟手柄驱动ViGEmBus完整教程
5分钟终极指南:Windows虚拟手柄驱动ViGEmBus完整教程 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 想要在Windows系统上享受专业级的游戏控制体…...
智能票务自动化工具:提升大型活动门票获取效率的全流程解决方案
智能票务自动化工具:提升大型活动门票获取效率的全流程解决方案 【免费下载链接】Automatic_ticket_purchase 大麦网抢票脚本 项目地址: https://gitcode.com/GitHub_Trending/au/Automatic_ticket_purchase 在数字化时代,大型展会、体育赛事等热…...
WarcraftHelper:让经典魔兽争霸III在现代电脑上焕发新生的全能助手
WarcraftHelper:让经典魔兽争霸III在现代电脑上焕发新生的全能助手 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为魔兽争霸III在宽…...
快速上手语音情感分析:Emotion2Vec+系统参数配置与结果解读
快速上手语音情感分析:Emotion2Vec系统参数配置与结果解读 1. 系统概述与核心价值 Emotion2Vec Large语音情感识别系统是一款基于深度学习的语音分析工具,能够自动识别语音中蕴含的情感状态。该系统由科哥团队基于阿里达摩院ModelScope平台的原始模型进…...
Phi-3-mini-128k-instruct实战:利用VLOOKUP逻辑进行多源数据关联与报告生成
Phi-3-mini-128k-instruct实战:利用VLOOKUP逻辑进行多源数据关联与报告生成 1. 引言 如果你用过Excel,肯定对VLOOKUP这个函数不陌生。它的核心就一句话:根据一个表格里的某个值,去另一个表格里找到对应的信息,然后“…...
快速体验WAN2.2文生视频:ComfyUI预置工作流,2分钟生成测试视频
快速体验WAN2.2文生视频:ComfyUI预置工作流,2分钟生成测试视频 1. 为什么选择WAN2.2文生视频工作流 如果你正在寻找一个简单易用、效果出色的文生视频工具,WAN2.2文生视频工作流绝对值得一试。这个预置在ComfyUI中的工作流,让视…...
DeerFlow效果展示:自动生成的深度研究报告与播客内容惊艳分享
DeerFlow效果展示:自动生成的深度研究报告与播客内容惊艳分享 1. DeerFlow核心能力概览 DeerFlow作为一款深度研究智能助手,整合了语言模型、网络搜索和代码执行能力,能够自动完成从信息收集到内容生成的全流程工作。其核心功能亮点包括&am…...
Go Module 依赖冲突调试方法
Go Module 依赖冲突调试方法 在Go语言开发中,依赖管理是一个关键环节。随着项目规模的扩大,依赖的第三方库越来越多,版本冲突问题也愈发常见。Go Module作为官方推荐的依赖管理工具,虽然简化了依赖管理流程,但在多级依…...
