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

前缀树（Trie）（字典树）

news 来源：原创 2025/5/26 5:32:24

做leetcode的时候看到前缀树，听都没听过，后来才知道前缀树就是字典树。之前学过，在OJ项目中用字典树来实现黑白名单限制。浅浅复习一下吧

用字典树来实现黑白名单限制实现步骤

（1）定义黑名单

import java.util.Arrays;
import java.util.List;private static final List<String> blackList = Arrays.asList("Files", "exec");

（2）初始化字典树

使用 HuTool 的 WordTree 初始化并插入黑名单中的单词。

import cn.hutool.core.text.WordTree;private static final WordTree WORD_TREE;static {// 初始化字典树WORD_TREE = new WordTree();// 插入黑名单中的单词WORD_TREE.addWords(blackList);
}

（3）校验用户代码

校验用户输入的代码是否包含黑名单中的禁用词。

// 校验代码中是否包含黑名单中的禁用词
FoundWord foundWord = WORD_TREE.matchWord(code);
if (foundWord != null) {System.out.println("包含禁止词：" + foundWord.getFoundWord());return null; // 或者抛出异常
}

（4）完整代码

import cn.hutool.core.text.WordTree;
import cn.hutool.core.text.WordTree.FoundWord;import java.util.Arrays;
import java.util.List;public class CodeValidator {// 定义黑名单private static final List<String> blackList = Arrays.asList("Files", "exec");// 初始化字典树private static final WordTree WORD_TREE;static {WORD_TREE = new WordTree();WORD_TREE.addWords(blackList);}// 校验用户代码public static String validateCode(String code) {// 校验代码中是否包含黑名单中的禁用词FoundWord foundWord = WORD_TREE.matchWord(code);if (foundWord != null) {System.out.println("包含禁止词：" + foundWord.getFoundWord());return null; // 或者抛出异常}return code; // 如果没有禁用词，返回代码}public static void main(String[] args) {String code = "System.out.println('Hello, World!');";String result = validateCode(code);if (result != null) {System.out.println("代码校验通过！");} else {System.out.println("代码校验失败！");}}
}

深入理解前缀树概念

1 定义

前缀树（Trie）是一种树形数据结构，用于高效地存储和检索字符串集合。它的每个节点表示一个字符，通过节点之间的连接来表示字符串。

2 结构特点

节点（Node）：

每个节点表示一个字符。
每个节点包含一个布尔值 isEnd，表示当前节点是否是一个单词的结尾。
每个节点包含一个数组（或哈希表）next，用于存储其子节点，对应于下一个字符。

根节点（Root Node）：

根节点不存储任何字符，但它是树的起点。
从根节点开始，通过路径上的字符可以拼接出完整的字符串。

3 前缀树的实现

1. Trie 类的定义

class Trie {private boolean isEnd; // 标记是否是单词结尾private Trie[] next;   // 存储子节点的数组public Trie() {isEnd = false; // 初始化时，当前节点不是单词结尾next = new Trie[26]; // 初始化一个大小为26的数组，对应26个小写字母}
}

2. 插入单词（insert 方法）

public void insert(String word) {Trie node = this; // 从根节点开始for (char c : word.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引if (node.next[index] == null) { // 如果当前字符对应的子节点不存在node.next[index] = new Trie(); // 创建一个新的 Trie 节点}node = node.next[index]; // 移动到子节点}node.isEnd = true; // 标记单词结尾
}

3. 搜索单词（`search` 方法）

public boolean search(String word) {Trie node = this; // 从根节点开始for (char c : word.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引node = node.next[index]; // 移动到子节点if (node == null) { // 如果子节点不存在return false; // 单词不存在}}return node.isEnd; // 检查最后一个节点是否是单词结尾
}

4. 搜索前缀（`startsWith` 方法）

public boolean startsWith(String prefix) {Trie node = this; // 从根节点开始for (char c : prefix.toCharArray()) {int index = c - 'a'; // 计算字符在数组中的索引node = node.next[index]; // 移动到子节点if (node == null) { // 如果子节点不存在return false; // 前缀不存在}}return true; // 前缀存在
}

前缀树（Trie）（字典树）

做leetcode的时候看到前缀树，听都没听过，后来才知道前缀树就是字典树。之前学过，在OJ项目中用字典树来实现黑白名单限制。浅浅复习一下吧用字典树来实现黑白名单限制实现步骤 （1）定义黑名单 import java.util.Arra…...

编程日记 2025/5/26 5:32:24

word插入APA格式的参考文献

word插入APA格式的参考文献并实现交叉引用 1. 直接手写并采用超链接 2. 使用zotero插入参考文献后采用超链接(前提下载zotero和对应的插件) 1. 直接手写 APA格式生成 1. 在需要插入参考文献的地方手写格式，如下。 2. 生成书签名字随便填的，&#x…...

编程日记 2025/4/29 6:59:33

n8n部署docker本地化备份和数据持久化和迁移问题

问题总结： 在一开始的操作中，你遇到的主要问题是 Docker 容器内的文件权限导致了文件无法正确写入和修改，尤其是在复制本地备份文件到容器内时。具体问题表现为： 复制文件后，容器内文件权限错误：你使用 do…...

编程日记 2025/4/29 6:59:32

绘制板块层级图

目录【实验目的】【实验原理】【实验环境】【实验步骤】【实验总结】【实验目的】掌握数据文件读取掌握数据处理的方法实现板块层级图的绘制【实验原理】板块层级图（treemap）是一种基于面积的可视化方式，通过每一个板块&…...

编程日记 2025/4/29 6:58:30

国标云台控制状态

1.基本概念国标联网系统的信息传输、交换、控制方面的都是通过SIP服务器负责通讯得，SIP负责信令流逐级转发。其中最重要的一部分就是和摄像机进行信令交互。像安全注册、实时视音频点播、历史视音频的回放等应用的会话控制采用IETFRFC3261规定的Register、Invite等…...

编程日记 2025/4/29 6:58:28

PostgreSQL与MySQL哪个适合做时空数据分析？

PostgreSQL与MySQL的定位与区别定位差异：功能导向与性能优先 PostgreSQL和MySQL作为两大主流开源数据库，其核心设计理念和适用场景存在显著差异。PostgreSQL定位为对象-关系型数据库（ORDBMS） ，强调功能完备性与标准…...

编程日记 2025/4/29 6:58:27

uniapp利用生命周期函数实现后台常驻示例

在 Uniapp 中，利用生命周期函数实现“后台常驻”主要是通过监听应用的前后台状态变化（ onHide 和 onShow ），并结合定时器、后台任务或状态保持逻辑来实现。但需注意： 纯前端 JS 代码无法突破系统对后台应用的限制&am…...

编程日记 2025/4/29 6:57:26

JAVA设计模式——（八）单例模式

JAVA设计模式——（八）单例模式介绍理解实现饿汉式懒汉式应用介绍确保一个类只存在一个实例。理解就是一个实例，new出来的一个，很简单。不过单例模式分为了懒汉式和饿汉式，其中也有线程安全的实现方式和线程不…...

编程日记 2025/4/29 6:57:26

【亚马逊云】AWS Wavelength 从理论讲解到实验演练

一、什么是 AWS Wavelength？ Wavelength——一种新型的 AWS 基础设施，旨在运行需要低延迟或边缘弹性的工作负载。 AWS Wavelength 将按需计算和存储服务引入通信服务提供商网络，使客户能够构建和部署满足其数据驻留、低延迟和弹性要求的应用…...

编程日记 2025/4/29 6:57:24

Uniapp：vite.config.js全局配置

目录一、基本概述二、配置自动引入插件一、基本概述 vite.config.js 是一个可选的配置文件，如果项目的根目录中存在这个文件，那么它会被自动加载，一般用于配置 vite 的编译选项二、配置自动引入插件在项目命令行终端中执行如下代码 npm install unplugin-auto-import…...

编程日记 2025/4/29 6:57:23

Springboot整合阿里云腾讯云发送短信验证码可随时切换短信运营商

本文描述了在springboot项目中整合实现对接阿里云和腾讯云的短信验证码发送，可通过更改配置文件达到切换短信发送运营商(申请签名、短信模版这些本文不在叙述)。首先看下大体结构： 一、需要导入的jar <dependency><groupId>com.…...

编程日记 2025/4/29 6:56:19

git 查看用户信息

在 Git 中查看用户信息是一项常见的任务，可以帮助你确认当前仓库的配置或全局的 Git 配置是否正确设置。你可以通过多种方式来查看这些信息。查看全局用户信息全局用户信息是应用于所有 Git 仓库的默认设置。要查看全局用户信息，可以使用以下命令&am…...

编程日记 2025/4/29 6:56:19

JAVA基础：Collections 工具类实战指南-从排序到线程安全

在 Java 开发中，集合类几乎贯穿每一个项目，而Collections工具类提供了一系列强大的方法，用于操作和增强集合的功能。无论是排序、查找还是线程安全的封装，Collections工具类都是提升代码效率和质量的重要工具。一、Collections …...

编程日记 2025/4/29 6:56:18

【计算机视觉】TorchVision 深度解析：从核心功能到实战应用 ——PyTorch 官方计算机视觉库的全面指南

TorchVision 深度解析：从核心功能到实战应用 ——PyTorch 官方计算机视觉库的全面指南 1. TorchVision 项目概览核心模块 2. 实战案例：10 大应用场景详解案例 1：使用预训练 ResNet 进行图像分类代码实现常见问题相关论文案例 2：加…...

编程日记 2025/4/29 6:55:17

case和字符串操作

使用if选择结构 if [];then elif [];then #注意这个地方,java是else if else ; fi 使用for循环结构使用for循环，语法结构如下所示： for 变量名 in 值1 值2 值3 #值的数量决定循环任务的次数 do命令序列 done#循环输出1到10 for i in {1..10} #注…...

编程日记 2025/4/29 6:55:15

Golang｜外观模式和具体逻辑

最终返回的是Document的切片，然后取得Bytes自己再去做反序列化拿到文档的各种详细信息。外观模式是一种结构型设计模式，它的目的是为复杂的子系统提供一个统一的高层接口，让外部调用者（客户端）可以更简单地使用子系统…...

编程日记 2025/4/29 6:55:15

关于kafka

1.为什么需要消息队列举个经典的例子。你是一个网购达人，经常在网上购物。快递小哥到了你的小区后，立刻给你打电话说：“你的快递到了，请马上来取。” 但你是一个合格的牛马，在上班，不方便取快递&#…...

编程日记 2025/4/29 6:55:13

OpenCV 图形API（67）图像与通道拼接函数-----水平拼接（横向连接）两个输入矩阵（GMat 类型）函数concatHor()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述该函数用于水平拼接两个 GMat 矩阵，要求输入矩阵的行数必须一致: GMat A { 1, 4,2, 5,3, 6 }; GMat B { 7, 10,8, 11,9, 12 }; GM…...

编程日记 2025/4/29 6:54:11

夜莺 v8.0.0-beta.10 部署

夜莺 v8.0.0-beta.10 部署 1. mariadb-server2. Redis安装3. 下载 n9e-v8.0.0-beta.10-linux-amd64.tar.gz设置 root 用户密码配置文件配置mariadb的登录密码导入数据库表结构配置为 systemd 启动服务重新加载 systemd配置日志访问夜莺VictoriaMetrics 时序数据库安装接入数据…...

编程日记 2025/4/29 6:54:10

HTML5好看的水果蔬菜在线商城网站源码系列模板7

文章目录 1.设计来源1.1 主界面1.2 关于我们界面1.3 商城界面1.4 商品信息界面1.5 我的账户界面1.6 联系我们界面 2.效果和源码2.1 动态效果2.2 源代码源码下载万套模板，程序开发，在线开发，在线沟通作者：xcLeigh 文章地址&#…...

编程日记 2025/4/29 6:54:10

优化问题中变量分类与作用分析

优化问题中的变量分类与作用在优化问题中，变量的定义和作用因问题类型和建模需求而异。以下从决策变量、控制变量的区别与联系出发，结合其他相关变量进行系统分析： 1. 决策变量（Decision Variables） 定义&#xff1a…...

编程日记 2025/4/29 6:54:08

RSS‘25｜CMU提出统一空中操作框架：以末端执行器为中心，无人机实现高精度遥操作

导读在科技飞速发展的当下，机器人技术不断拓展其应用边界，空中操作领域成为了研究的热点之一。无人空中操纵器（UAMs）凭借其在高空复杂任务中的巨大潜力，正逐渐改变着诸如高空设备维护、桥梁检测等传统行业的作业模式&a…...

编程日记 2025/4/29 6:54:07

智能指针之设计模式6

本系列文章探讨了智能指针和设计模式的关系，前面五篇文章介绍的是使用设计模式实现了智能指针的相关特性，比如使用工厂模式控制了智能指针对象的创建，使用代理模式控制了资源对象的销毁。本文介绍一下使用智能指针来帮助我们实现相关的设计模…...

编程日记 2025/4/29 6:54:06

【设计模式】GOF概括

一、创建型模式（5种） 1. 单例模式 (Singleton) 适用场景：全局唯一实例（如配置管理、日志工具）。C示例：// 所谓的scott mayer单例模式 class Singleton { public:static Singleton& getInstance() {st…...

编程日记 2025/4/29 6:54:05

深入浅出限流算法（三）：追求极致精确的滑动日志

在限流的世界里，精度往往是关键。我们已经讨论过固定窗口（简单但有突刺）和滑动窗口（更平滑但仍有格子边界）。如果我们需要更精确的控制，滑动日志 (Sliding Log) 算法便登场了。核心思想：记录每…...

编程日记 2025/4/29 6:53:04

一文读懂Tomcat应用之 CentOS安装部署Tomcat服务

目录一、Tomcat概述 (一)、Tomcat安装目录简介 (二)、Tomcat配置文件简介 1、server.xml文件 2、web.xml 3、context.xml 4、tomcat-users.xml 5、logging.properties 二、Tomcat安装部署 (一)、环境规划 (二)、安装JDK 1、下载JDK二进制安装包 2、解压JDK二进制…...

编程日记 2025/4/29 6:53:03

JVM 内存分配策略

引言在 Java 虚拟机（JVM）中，内存分配与垃圾回收是影响程序性能的核心机制。内存分配的高效性直接决定了对象创建的速率，而垃圾回收策略则决定了内存的利用率以及系统的稳定性。为了在复杂多变的应用场景中实现高效的内存管理&am…...

编程日记 2025/4/29 6:53:03

轻松上手：使用 Docker Compose 部署 TiDB 的简易指南

作者：ShunWah 在运维管理领域，我拥有多年深厚的专业积累，兼具坚实的理论基础与广泛的实践经验。精通运维自动化流程，对于OceanBase、MySQL等多种数据库的部署与运维，具备从初始部署到后期维护的全链条管理能力。拥有Oc…...

编程日记 2025/4/29 6:53:02

Linux权限管理

权限的概念在 Linux 系统里，权限管理是系统安全的关键环节。权限管理的核心目的是明确不同用户对文件和目录的操作许可范围，以此来保障系统资源的安全与合理使用。权限管理涉及三种不同的用户角色和三种基本的操作权限。用户角色所有者&#xff08…...

编程日记 2025/4/29 6:53:02

Crusader Kings III 王国风云 3（十字军之王 3） [DLC 解锁] [Steam] [Windows SteamOS macOS]

Crusader Kings III 王国风云 3（十字军之王 3） [DLC 解锁] [Steam] [Windows & SteamOS & macOS] DLC 版本至最新全部 DLC 后续可能无法及时更新文章，具体最新版本见下载文件说明； DLC 解锁列表（仅供参考&am…...

编程日记 2025/4/29 6:53:01

架构风格对比

架构风格深度对比：从管道-过滤器到微内核 📜 引言在软件架构设计中，不同的架构风格适用于不同的业务场景。本文将深入解析 7种主流架构风格，包括它们的核心思想、优缺点、适用场景，并通过对比表格和示例帮助您选择最…...

编程日记 2025/4/29 6:53:00

V Rising 夜族崛起 [DLC 解锁] [Steam] [Windows SteamOS]

V Rising 夜族崛起 [DLC 解锁] [Steam] [Windows & SteamOS] 注意这个符号表示可打开折叠内容需要有游戏正版基础本体，安装路径不能带有中文，或其它非常规拉丁字符；仅限用于自建服务器，并禁用 VAC ！&#xff0…...

编程日记 2025/4/29 6:53:00

HTML标记语言_@拉钩教育

目录 1.文本标签 2.格式化标签 3.图片标签 4.超链接标签 5.表格标签 6表单标签 6.1 6.2 6.3 7.行内框架(超链接内套一个页面) 8.多媒体标签(音/视频) 1.文本标签 2.格式化标签 3.图片标签 4.超链接标签 5.表格标签 6表单标签 6.1 6.2 6.3 7.行内框架(超链接内套一个…...

编程日记 2025/4/29 6:52:59

云原生开发革命：iVX 如何实现 “资源即插即用” 的弹性架构？

云原生技术正以惊人的速度重塑软件开发的版图。短短几年间，它从少数技术先驱的实验性方案，迅速崛起为全球企业数字化转型的核心驱动力。Gartner 预测，到 2026 年，全球 85% 的企业将全面采用云原生技术进行应用开发与部署。云原生架…...

编程日记 2025/4/29 6:51:57

whois为什么有时会返回两个不同的域名状态

前阵子发现一直想注册但被别人注册了的一个域名快要过期了，就想着写个脚本跑在电脑上，每分钟检查一次域名状态，一旦域名被正式删除，就发封邮件通知我，这样就不用频繁手动检查域名状态了。写脚本时发现一个有趣的现象…...

编程日记 2025/5/24 22:31:58

跨境电商店铺矩阵布局：多账号运营理论到实操全解析

在当今竞争激烈的全球电商市场中，跨境电商店铺矩阵布局已成为卖家脱颖而出的关键策略。本文将深入剖析跨境电商店铺矩阵布局的本质、优势，并提供从理论到实操的全方位指导，助力您在全球市场中开启属于自己的销售新篇章。一、是什么&#xff…...

编程日记 2025/5/18 2:30:24

安卓基础（强制转换）

一、强制转换（Type Casting） 1. 什么是强制转换？ 当你想将一个类型的对象转换为另一个类型时，如果它们之间存在继承关系，就需要强制转换。注意：只有存在继承关系的类型…...

编程日记 2025/5/17 23:26:21

VS2022+OpenCasCade配置编译

一、Open CASCADE Technology介绍及安装（windows10） Open CASCADE Technology（简称OCCT）是一款开源的 3D CAD/CAM/CAE 软件开发平台，广泛应用于工业设计、工程仿真、制造等领域。开源OCC对象库是一个面向对象C类库&…...

编程日记 2025/5/16 2:52:11

AIGC重构元宇宙：从内容生成到沉浸式体验的技术革命

1. 引言当数字技术掀开人类交互的新篇章，元宇宙正从科幻构想蜕变为现实——这个由虚拟与现实交织的数字宇宙，承载着未来社会的娱乐、工作与社交形态。作为核心赋能技术，AIGC（人工智能生成内容）正以惊人的创造力&…...

编程日记 2025/5/3 9:01:53

当所有人都用上先进ai，如何保持你的优势？

这不再是你能用上openai模型别人只能用文心一言的时候，而是每个人都可以免费用deepseek r1的时代。如今，办公室里每个人都能随时调用deepseek模型，喊一声“帮我写段代码”便轻松解决问题。在这种情况下，单纯“会用AI”已经很难再形…...

编程日记 2025/4/29 6:49:46

【浙江大学DeepSeek公开课】人类经验与AI算法的镜像之旅

人类经验与AI算法的镜像之旅人类经验与 AI 算法的镜像之旅一、语言的奥秘：人类如何解码世界二、从符号到智能：AI 的语言理解之路三、DeepSeek - V3：大语言模型的构建与进化四、DeepSeek - R1：推理模型的诞生与突破五、智能体时代…...

编程日记 2025/5/16 7:28:02

【前端】从零开始的搭建顺序指南（技术栈：Node.js + Express + MongoDB + React）book-management

项目路径总结后端结构 server/ ├── controllers/ # 业务逻辑 │ ├── authController.js │ ├── bookController.js │ ├── genreController.js │ └── userController.js ├── middleware/ # 中间件 │ ├── authMiddleware…...

编程日记 2025/4/29 6:49:45

探针台维护方法

探针台的维护直接影响其测试精度与使用寿命，需结合日常清洁、环境控制、定期校准等多维度操作，具体方法如下： 一、日常清洁与保养 1.‌表面清洁‌ 使用无尘布或软布擦拭探针台表面，避免残留清洁剂或硬物划伤精密部件。探针头清…...

编程日记 2025/5/15 13:20:35

js day8

事件绑定事件：发生在html元素上的特定动作，鼠标点击，键盘按下，鼠标移入事件三要素：事件源（触发事件的元素） 事件类型，事件触发后执行的函数通过html触发事件（不建议…...

编程日记 2025/4/29 6:48:40

大模型训练平台：重构 AI 研发范式的智慧基建

当 AI 研发陷入“高耗低效”困局，如何破局？ 在大模型技术爆发的今天，企业 AI 研发正面临前所未有的挑战：某金融机构为训练风控模型投入大量算力，却因数据标注耗时半年延误项目；某制造企业搭建的训练集群利…...

编程日记 2025/4/29 6:48:39

安装 npm install -S vuex-persist（yarn add vuex-persist） 使用： /store/index.js引入vuex-persist配置： import Vue from vue import Vuex from vuex import VuexPersistence from vuex-persist import user from ./modules/use…...

编程日记 2025/5/7 7:15:27