数据结构笔记--前缀树的实现
1--前缀树的实现
前缀树的每一个节点拥有三个成员变量,pass表示有多少个字符串经过该节点,end表示有多少个字符串以该节点结尾,nexts表示该字符串可以走向哪些节点;
#include <iostream>
#include <unordered_map>struct TreeNode{TreeNode() : pass(0), end(0){}int pass; // 经过次数int end; // 是多少个字符串的结尾std::unordered_map<char, TreeNode*> nexts;
};class Trie{
public:// 构造函数Trie(){root = new TreeNode();}void insert(std::string word){if(word.length() == 0) return;TreeNode *node = root;node->pass++;for(int i = 0; i < word.length(); i++){if(node->nexts[word[i]] == NULL){ // 哈希表中没有该字符node->nexts[word[i]] = new TreeNode(); // 新建该字符}node = node->nexts[word[i]];node->pass++; // 该字符节点经过的次数++}node->end++; // 遍历word末尾时,节点的end++,表明以该节点结尾的字符串数++}bool search(std::string word){if(word.length() == 0) return true;TreeNode *cur = root;for(int i = 0; i < word.length(); i++){if(cur->nexts[word[i]] == NULL) return 0; // 没有该字符节点cur = cur->nexts[word[i]];}return cur->end; // end不为0表明该字符串出现过}bool startWith(std::string prefix){if(prefix.length() == 0) return 0;TreeNode *cur = root;for(int i = 0; i < prefix.length(); i++){if(cur->nexts[prefix[i]] == NULL) return 0; // 前缀没出现过cur = cur->nexts[prefix[i]];}return cur->pass; // 有多少个字符串经过该前缀,0个表明false;}private:TreeNode *root;
};int main(int argc, char *argv[]){Trie T1;std::string test1 = "hello";T1.insert(test1);bool res1 = T1.search(test1);if(res1) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;bool res2 = T1.startWith("hel");if(res2) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}
2--LeetCode真题
2-1--实现Trie(前缀树)

本题不能自定义节点,因此将 pass、end 和 nexts 等成员变量转换成类的成员变量,新节点就是类的对象;
class Trie{
public:// 构造函数Trie(){}void insert(std::string word){if(word.length() == 0) return;Trie *node = this;node->pass++;for(int i = 0; i < word.length(); i++){if(node->nexts[word[i]] == NULL){ // 哈希表中没有该字符node->nexts[word[i]] = new Trie(); // 新建该字符}node = node->nexts[word[i]];node->pass++; // 该字符节点经过的次数++}node->end++; // 遍历word末尾时,节点的end++,表明以该节点结尾的字符串数++}bool search(std::string word){if(word.length() == 0) return true;Trie *cur = this;for(int i = 0; i < word.length(); i++){if(cur->nexts[word[i]] == NULL) return 0; // 没有该字符节点cur = cur->nexts[word[i]];}return cur->end; // end不为0表明该字符串出现过}bool startsWith(std::string prefix){if(prefix.length() == 0) return 0;Trie *cur = this;for(int i = 0; i < prefix.length(); i++){if(cur->nexts[prefix[i]] == NULL) return 0; // 前缀没出现过cur = cur->nexts[prefix[i]];}return cur->pass; // 有多少个字符串经过该前缀,0个表明false;}private:int pass = 0; // 经过次数int end = 0; // 是多少个字符串的结尾std::unordered_map<char, Trie*> nexts;
};
相关文章:
数据结构笔记--前缀树的实现
1--前缀树的实现 前缀树的每一个节点拥有三个成员变量,pass表示有多少个字符串经过该节点,end表示有多少个字符串以该节点结尾,nexts表示该字符串可以走向哪些节点; #include <iostream> #include <unordered_map>str…...
C/C++时间获取函数
time.h包含C/C中用于获取时间,和时间转换方面的函数。 1、time() 函数 time_t time(time_t *seconds) 返回自(1970-01-01 00:00:00 UTC)起经过的时间,以秒为单位。如果 seconds 不为空,则返回值也存储在变量 seconds …...
sql中判断日期是否是同一天
sql中判断日期是否是同一天的sql sql: select id,product_id,seckill_price,stock_count,time,intergral,start_date from t_seckill_product where to_days(start_date) to_days(now()) to_days函数: 使用to_days(start_date) to_days(now())的方式是一种常见的…...
NAS搭建指南一——服务器的选择与搭建
一、服务器的选择 有自己的本地的公网 IP 的请跳过此篇文章按需求选择一个云服务器,目的就是为了进行 frp 的搭建,完成内网穿透我选择的是腾讯云服务器,我的配置如下,仅供参考: 4. 腾讯云服务器官网地址 二、服务器…...
豪越HYDO智能运维助力智慧医院信息化建设
随着国家政策的推动与支持,医疗行业信息化应用不断普及,大数据、AI、医疗物联网等技术的应用,快速推动了电子病历、智慧服务、智慧管理的智慧医院建设和医院信息标准化建设,通过不断探索创新“智慧医院”服务模式,实现…...
Week1题目重刷
今天把week1的题目都重新刷了一遍,明天开始week2的内容~ 704.二分查找 class Solution {public int search(int[] nums, int target) {int l 0, r nums.length - 1, m;while (l < r) {m (l r) >>> 1;if (nums[m] < target) {l m 1;} else if…...
考研数据结构:第七章 查找
文章目录 一、查找的基本概念二、顺序查找和折半查找2.1顺序查找2.3折半查找2.3.1算法思想2.3.2代码实现2.3.3查找效率分析2.3.4折半查找判定树的构造2.3.5折半查找效率2.3.6小结 2.4分块查找 三、树形查找3.1二叉排序树3.1.1二叉排序树定义3.1.2查找操作3.1.3插入操作3.1.4二叉…...
【Linux进程篇】环境变量
【Linux进程篇】环境变量 目录 【Linux进程篇】环境变量基本概念常见环境变量查看环境变量方法测试PATH测试HOME测试SHELL和环境变量相关的命令环境变量的组织方式通过代码如何获取环境变量命令行参数命令行第三个参数通过第三方变量environ获取 本地变量通过系统调用获取或设置…...
【软件测试】Linux环境下Docker搭建+Docker搭建MySQL服务(详细)
目录:导读 前言 一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 Linux之docker搭…...
去了字节跳动,才知道年薪40W的测试有这么多?
今年大环境不好,内卷的厉害,薪资待遇好的工作机会更是难得。最近脉脉职言区有一条讨论火了: 哪家互联网公司薪资最‘厉害’? 下面的评论多为字节跳动,还炸出了很多年薪40W的测试工程师 我只想问一句,现在的…...
linux0.95(VFS重点)源码通俗解读(施工中)
文件系统在磁盘中的体现 下面是磁盘的内容,其中i节点就是一个inode数组,逻辑块就是数据块可用于存放数据 操作系统通过将磁盘数据读入到内存中指定的缓冲区块来与磁盘交互,对内存中的缓冲区块修改后写回磁盘。 进程(task_struct * task[N…...
mac ssh连接另一台window虚拟机vm
vmware配置端口映射 编辑(E) > 虚拟网络编辑器(N)... > NAT设置(S)... window防火墙,入站规则添加5555端口 控制面板 > 系统和安全 > Windows 防火墙>高级设置>入站规则>新建规则... tips windows查看端口命令:netstat -ano | f…...
使用Python解析通达信本地lday数据结构
通达信软件中的vipdoc是一个存储股票行情数据的文件夹。在通达信软件的安装目录下,可以找到一个名为vipdoc的文件夹,里面存放着各个股票的分时、日线、周线、月线等行情数据文件。这些数据文件可以用于自定义分析和回测股票的走势和交易策略,…...
【Mysql】修改definer
修改definer 本文介绍如何修改MySQL中的function、procedure、event、view和trigger的definer 修改function、procedure的definer 首先,我们需要登录MySQL命令行界面,然后执行以下命令: select definer from mysql.proc;这个命令会列出所…...
图片预览插件vue-photo-preview的使用
移动端项目中需要图片预览的功能,但本身使用mintui,vantui中虽然也有,但是为了一个组件安装这个有点儿多余,就选用了vue-photo-preview插件实现(其实偷懒也不想自己写)。 1、安装 npm i vue-photo-preview…...
最强自动化测试框架Playwright(20)- iframe
一个页面可以附加一个或多个 Frame 对象。每个页面都有一个主框架,并且假定页面级交互(如)在主框架中运行。click frame_locator 使用 iframe 时,可以创建一个框架定位器,该定位器将进入 iframe 并允许选择该 iframe…...
leetcode 516. 最长回文子序列(JAVA)题解
题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_sourceLCUS&utm_mediumip_redirect&utm_campaigntransfer2china 目录 题目描述: 暴力递归: 动态规划: 题目描述: 给你一个…...
在Java中操作Redis(详细-->从环境配置到代码实现)
在Java中操作Redis 文章目录 在Java中操作Redis1、介绍2、Jedis3、Spring Data Redis3.1、对String的操作3.2、对哈希类型数据的操作3.3、对list的操作3.4、对set类型的操作3.5、对 ZSet类型的数据(有序集合)3.6、通用类型的操作 1、介绍 Redis 的Java客…...
分布式作业调度框架——ElasticJob
1、简介 ElasticJob 是面向互联网生态和海量任务的分布式调度解决方案,由两个相互独立的子项目 ElasticJob-Lite 和 ElasticJob-Cloud 组成。 它通过弹性调度、资源管控、以及作业治理的功能,打造一个适用于互联网场景的分布式调度解决方案,…...
react如何实现数据渲染
React数据渲染是指将组件中的数据映射到页面上,以展示出来。在React中,数据渲染通常是通过JSX和组件的state或props完成的。 JSX是一个类似HTML的语法,可以在其中嵌入JavaScript表达式。在JSX中,可以使用{}包裹JavaScript表达式&…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...
