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

【高级数据结构】Trie树

原理

介绍

高效地存储和查询字符串的数据结构。所以其重点在于:存储、查询两个操作。

存储操作

示例和图片来自:https://blog.csdn.net/qq_42024195/article/details/88364485

假设有这么几个字符串:b,abc,abd,bcd,abcd,efg,hii。最终存储出来的Trie图如下图所示:

在这里插入图片描述
具体是怎么存的呢?对于每一个字符串,从树的根节点开始,依次判断当前节点的儿子节点中是否有当前字符:

  • 如果有,则进行下一个字符的判断,同时根节点更新为该儿子节点
  • 如果没有,创建一个儿子节点为当前字符,然后根节点更新为该儿子节点

如果已经到了最后一个字符,就在对应的儿子节点进行一个标记,表示从根节点到该节点的字符组成的字符串是一个单词。(对应图中的红色部分)

查询

查询和存储的操作类似。对于一个给定的字符串,从树的根节点开始,依次判断当前节点的儿子节点中是否有当前字符:

  • 如果有,则进行下一个字符的判断,同时根节点更新为该儿子节点
  • 如果没有,则说明不存在该字符串,直接返回不存在

复杂度

时间复杂度:O(max_len(s))=O(h),h为Trie树的高度,即最长字符串的长度。

空间复杂度:不超过O(N * max_len(s))。

代码实现

208. 实现 Trie (前缀树)

class Trie {private Trie[] children; // 当前节点的所有儿子private boolean isEnd; // 当前节点是否为一个单词的结尾public Trie() {children = new Trie[26]; // 假设字符串中都是小写字母,那么一个节点的所有儿子最多只有26个isEnd = false;}/**存储操作:插入一个字符串*/public void insert(String word) {Trie node = this; // 从根节点开始for(char c : word.toCharArray()) {int u = c - 'a'; // [a, z] -> [0, 25]if (node.children[u] == null) { // 当前节点node不存在儿子节点 node.children[u] = new Trie(); // 创建一个节点为当前字符} node = node.children[u]; // 更新根节点为儿子节点}node.isEnd = true;}/**查询操作:查询某个字符串是否在树中。如果在树中,可以是树中单词的前缀,也可以是完整的单词*/private Trie searchPrefix(String prefix) {Trie node = this; // 从根节点开始for(char c : prefix.toCharArray()) {int u = c - 'a'; // [a, z] -> [0, 25]if (node.children[u] == null) { // 当前节点node不存在儿子节点 return null;} node = node.children[u]; // 走到儿子节点}return node;}public boolean search(String word) {// 查询树中是否存在完整的单词Trie node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {// 查询树中是否存在某个前缀return searchPrefix(prefix) != null;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

当然,Trie树也可以查询存储并查询一个单词出现了几次,只需要把isEnd改成cnt就行。当cnt为0时,表示没出现过,即不是一个完整的单词;当cnt > 0时,表示出现过,cnt的大小即为出现的次数。

相关文章:

【高级数据结构】Trie树

原理 介绍 高效地存储和查询字符串的数据结构。所以其重点在于:存储、查询两个操作。 存储操作 示例和图片来自:https://blog.csdn.net/qq_42024195/article/details/88364485 假设有这么几个字符串:b,abc,abd&…...

国际化 Vue-i18n的安装与使用 (Vue2.0 / Vue3.0)

国际化 Vue-i18n的安装与使用 (Vue2.0 / Vue3.0) 一、Vue-i18n是什么? Vue-I18n是 Vue.js 的国际化插件。它可以轻松地将一些本地化功能集成到你的 Vue.js 应用程序中。简单来说就是可以帮助用户进行语言的切换” 二、使用步骤 1.引入库 代码…...

Linux 学习笔记(8)

八、 启动引导 1 、 Linux 的启动流程 1) BIOS 自检 2) 启动 GRUB/LILO 3) 运行 Linux kernel 并检测硬件 4) 挂载根文件系统 5) 运行 Linux 系统的第一个进程 init( 其 PID 永远为 1 ,是所有其它进程的父进程 ) 6) init 读取系统引导配置文件…...

【python】1.python3.12.2和pycharm社区版的安装指南

欢迎来CILMY23的博客喔,本篇为【python】1.python3.12.2和pycharm社区版的安装指南,感谢观看,支持的可以给个一键三连,点赞关注收藏。 目录 一、python3.12.2的下载与安装 1.1下载 1.2安装 二、pycharm的安装 2.1下载安装 2…...

Ubuntu将c++编译成.so文件并测试

一、准备cpp和h文件 创建test.cpp 在cpp中定义相加的函数funcAdd&#xff0c;给出函数的细节代码 #include <iostream> using namespace std;int funcAdd(int x, int y) {return xy; }创建test.h 在h中声明定义的函数&#xff0c;不需要任何细节 #ifndef __TEST__ #…...

数据分析-Pandas数据的探查面积图

数据分析-Pandas数据的探查面积图 数据分析和处理中&#xff0c;难免会遇到各种数据&#xff0c;那么数据呈现怎样的规律呢&#xff1f;不管金融数据&#xff0c;风控数据&#xff0c;营销数据等等&#xff0c;莫不如此。如何通过图示展示数据的规律&#xff1f; 数据表&…...

美团分布式 ID 框架 Leaf 介绍和使用

一、Leaf 在当今日益数字化的世界里&#xff0c;软件系统的开发已经成为了几乎所有行业的核心。然而&#xff0c;随着应用程序的规模不断扩大&#xff0c;以及对性能和可扩展性的需求不断增加&#xff0c;传统的软件架构和设计模式也在不断地面临挑战。其中一个主要挑战就是如…...

Ubuntu20.04: UE4.27 中 Source Code 的编辑器下拉框没有 Rider选项

问题描述 最近想用 Rider 作为 UE4 开发的 IDE&#xff0c;但安装好 Rider 后&#xff0c;发现编辑器下拉框中没有 Rider 的选项&#xff0c;我检查了 UE4 的插件&#xff0c;发现 Rider Integration 插件已经安装且启用的。 环境&#xff1a;Ubuntu 20.04 UE4.27 Rider2023…...

【论文阅读-PRIVGUARD】Day4:3节

3 PRIVANALYZER&#xff1a;强制执行隐私政策的静态分析 本节介绍PRIVANALYZER&#xff0c;这是一个用于强制执行由PRIVGUARD追踪的隐私政策的静态分析器**。我们首先回顾LEGALEASE政策语言&#xff0c;我们使用它来正式编码政策&#xff0c;然后描述如何静态地强制执行它们**…...

新一代电话机器人开源PHP源代码

使用easyswoole 框架开发的 新一代电话机器人开源PHP源码 项目地址&#xff1a;https://gitee.com/ddrjcode/robotphp 代理商页面演示地址 http://119.23.229.15:8080 用户名&#xff1a;c0508 密码&#xff1a;123456 包含 AI外呼管理&#xff0c;话术管理&#xff0c;CR…...

dockerdocker-copose_限制容器cpu和内存

本文目录 docker的限制方式限制CPU占用限制内存占用 docker-compose docker的限制方式 限制CPU占用 Docker使用--cpus参数来限制容器的CPU资源。该参数指定了分配给容器的CPU核心数量或百分比。 例子&#xff1a;限制CPU使用个数 docker run --cpus2 <imageName>以上…...

【leetcode】圆圈中最后剩下的数字

目录 1. 问题 2. 思路 3. 代码 4. 运行 1. 问题 本题即为典型的约瑟夫问题&#xff0c;通过递推公式倒推出问题的解。原始问题是从n个人中每隔m个数踢出一个人&#xff0c;原始问题变成从n-1个人中每隔m个数踢出一个人…… 示例 1&#xff1a; 输入: n 5, m 3 输出: 3…...

利用python批量将.shp文件转换坐标生成.geojson文件,再将.geojson转换成.csv文件,最后将csv文件插入数据库表

第一步&#xff1a;.shp批量转.geojson # author: JMY # 创建时间: 2024/2/26 17:12 # 批量将.shp文件生成geojson文件并转换坐标为3857import os import geopandas as gpd# 定义输入和输出文件夹路径 input_folder shp文件 output_folder geojson文件# 定义输入和输出坐标系…...

远程服务器Ubuntu 18.04安装VNC远程桌面

一、安装vnc 1.安装图形化界面工具 # 安装过程中会弹窗让选择配置&#xff0c;选lightdm sudo apt install ubuntu-desktop sudo apt-get install gnome-panel gnome-settings-daemon metacity nautilus gnome-terminal 2.安装vnc sudo apt-get install x11vnc3.安装LightD…...

30天自制操作系统(第23天)

23.1 编写malloc 参考第22天的内容&#xff0c;在绘制窗口前先分配了150*50个字节大小的内存&#xff0c;所以导致该文件经编译后有7.6k左右&#xff0c;能否在其中使用指针呢&#xff1f;当需要开辟空间时&#xff0c;移动指针即可。在之前的章节中也有函数memman_alloc函数可…...

基于Rust语言,和WebAssembly技术,与JavaScript结合,的具体应用场景

基于Rust语言与WebAssembly&#xff08;Wasm&#xff09;技术并与JavaScript结合&#xff0c;可以应用于多个场景&#xff0c;特别是在需要高性能和/或低级系统访问的情况下。下面是一些具体的应用场景&#xff1a; 性能密集型任务: Rust加上Wasm适合执行计算密集型任务&#x…...

【MATLAB源码-第154期】基于matlab的OFDM系统多径信道下块状和梳妆两种导频插入方式误码率对比仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 OFDM&#xff08;Orthogonal Frequency Division Multiplexing&#xff0c;正交频分复用&#xff09;是一种高效的无线信号传输技术&#xff0c;广泛应用于现代通信系统&#xff0c;如Wi-Fi、LTE和5G。OFDM通过将宽带信道划分…...

Linux 下 socket 编程介绍及 TCP 客户端与服务端创建示例

目录 socket 编程接口TCP 服务端TCP 客户端更多内容 本文介绍了 Linux 下的 socket 编程&#xff0c;及总结了使用 socket 接口实现 TCP 服务端和客户端的示例代码。 socket 编程接口 socket() 函数&#xff1a;用于创建一个新的 socket 描述符&#xff1a; int socket(int …...

JetBrains Gateway Github Copilot 客户端插件和主机插件

JetBrains Gateway可以通过插件支持Github Copilot&#xff08;需另行注册&#xff09;。 需要安装插件 客户端&#xff0c;而非插件 主机&#xff0c;如图所示&#xff1a; 大概是因为代码显示在客户端&#xff08;运行在本地的IDE&#xff09;&#xff1f;...

【web APIs】3、(学习笔记)有案例!

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、概念其他事件页面加载事件元素滚动事件页面尺寸事件 元素尺寸与位置 二、案例举例电梯导航 前言 掌握阻止事件冒泡的方法理解事件委托的实现原理 一、概念…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...