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

数据结构笔记--前缀树的实现

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--前缀树的实现 前缀树的每一个节点拥有三个成员变量&#xff0c;pass表示有多少个字符串经过该节点&#xff0c;end表示有多少个字符串以该节点结尾&#xff0c;nexts表示该字符串可以走向哪些节点&#xff1b; #include <iostream> #include <unordered_map>str…...

C/C++时间获取函数

time.h包含C/C中用于获取时间&#xff0c;和时间转换方面的函数。 1、time() 函数 time_t time(time_t *seconds) 返回自&#xff08;1970-01-01 00:00:00 UTC&#xff09;起经过的时间&#xff0c;以秒为单位。如果 seconds 不为空&#xff0c;则返回值也存储在变量 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函数&#xff1a; 使用to_days(start_date) to_days(now())的方式是一种常见的…...

NAS搭建指南一——服务器的选择与搭建

一、服务器的选择 有自己的本地的公网 IP 的请跳过此篇文章按需求选择一个云服务器&#xff0c;目的就是为了进行 frp 的搭建&#xff0c;完成内网穿透我选择的是腾讯云服务器&#xff0c;我的配置如下&#xff0c;仅供参考&#xff1a; 4. 腾讯云服务器官网地址 二、服务器…...

豪越HYDO智能运维助力智慧医院信息化建设

随着国家政策的推动与支持&#xff0c;医疗行业信息化应用不断普及&#xff0c;大数据、AI、医疗物联网等技术的应用&#xff0c;快速推动了电子病历、智慧服务、智慧管理的智慧医院建设和医院信息标准化建设&#xff0c;通过不断探索创新“智慧医院”服务模式&#xff0c;实现…...

Week1题目重刷

今天把week1的题目都重新刷了一遍&#xff0c;明天开始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服务(详细)

目录&#xff1a;导读 前言 一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 Linux之docker搭…...

去了字节跳动,才知道年薪40W的测试有这么多?

今年大环境不好&#xff0c;内卷的厉害&#xff0c;薪资待遇好的工作机会更是难得。最近脉脉职言区有一条讨论火了&#xff1a; 哪家互联网公司薪资最‘厉害’&#xff1f; 下面的评论多为字节跳动&#xff0c;还炸出了很多年薪40W的测试工程师 我只想问一句&#xff0c;现在的…...

linux0.95(VFS重点)源码通俗解读(施工中)

文件系统在磁盘中的体现 下面是磁盘的内容&#xff0c;其中i节点就是一个inode数组&#xff0c;逻辑块就是数据块可用于存放数据 操作系统通过将磁盘数据读入到内存中指定的缓冲区块来与磁盘交互&#xff0c;对内存中的缓冲区块修改后写回磁盘。 进程(task_struct * task[N…...

mac ssh连接另一台window虚拟机vm

vmware配置端口映射 编辑(E) > 虚拟网络编辑器(N)... > NAT设置(S)... window防火墙&#xff0c;入站规则添加5555端口 控制面板 > 系统和安全 > Windows 防火墙>高级设置>入站规则>新建规则... tips windows查看端口命令&#xff1a;netstat -ano | f…...

使用Python解析通达信本地lday数据结构

通达信软件中的vipdoc是一个存储股票行情数据的文件夹。在通达信软件的安装目录下&#xff0c;可以找到一个名为vipdoc的文件夹&#xff0c;里面存放着各个股票的分时、日线、周线、月线等行情数据文件。这些数据文件可以用于自定义分析和回测股票的走势和交易策略&#xff0c;…...

【Mysql】修改definer

修改definer 本文介绍如何修改MySQL中的function、procedure、event、view和trigger的definer 修改function、procedure的definer 首先&#xff0c;我们需要登录MySQL命令行界面&#xff0c;然后执行以下命令&#xff1a; select definer from mysql.proc;这个命令会列出所…...

图片预览插件vue-photo-preview的使用

移动端项目中需要图片预览的功能&#xff0c;但本身使用mintui&#xff0c;vantui中虽然也有&#xff0c;但是为了一个组件安装这个有点儿多余&#xff0c;就选用了vue-photo-preview插件实现&#xff08;其实偷懒也不想自己写&#xff09;。 1、安装 npm i vue-photo-preview…...

最强自动化测试框架Playwright(20)- iframe

一个页面可以附加一个或多个 Frame 对象。每个页面都有一个主框架&#xff0c;并且假定页面级交互&#xff08;如&#xff09;在主框架中运行。click frame_locator 使用 iframe 时&#xff0c;可以创建一个框架定位器&#xff0c;该定位器将进入 iframe 并允许选择该 iframe…...

leetcode 516. 最长回文子序列(JAVA)题解

题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_sourceLCUS&utm_mediumip_redirect&utm_campaigntransfer2china 目录 题目描述&#xff1a; 暴力递归&#xff1a; 动态规划&#xff1a; 题目描述&#xff1a; 给你一个…...

在Java中操作Redis(详细-->从环境配置到代码实现)

在Java中操作Redis 文章目录 在Java中操作Redis1、介绍2、Jedis3、Spring Data Redis3.1、对String的操作3.2、对哈希类型数据的操作3.3、对list的操作3.4、对set类型的操作3.5、对 ZSet类型的数据&#xff08;有序集合&#xff09;3.6、通用类型的操作 1、介绍 Redis 的Java客…...

分布式作业调度框架——ElasticJob

1、简介 ElasticJob 是面向互联网生态和海量任务的分布式调度解决方案&#xff0c;由两个相互独立的子项目 ElasticJob-Lite 和 ElasticJob-Cloud 组成。 它通过弹性调度、资源管控、以及作业治理的功能&#xff0c;打造一个适用于互联网场景的分布式调度解决方案&#xff0c;…...

react如何实现数据渲染

React数据渲染是指将组件中的数据映射到页面上&#xff0c;以展示出来。在React中&#xff0c;数据渲染通常是通过JSX和组件的state或props完成的。 JSX是一个类似HTML的语法&#xff0c;可以在其中嵌入JavaScript表达式。在JSX中&#xff0c;可以使用{}包裹JavaScript表达式&…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...