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

字典树(前缀树)数组实现(只能查26个单词)

这段代码实现了一个基于 Trie 树的字典树(Trie)数据结构,用于存储和检索字符串。其中包含以下几个方法.
insert(String word): 向 Trie 树中插入一个单词。首先将单词转换为字符数组,然后遍历字符数组,逐个字符在 Trie 树中创建节点。每建一个节点,就将该节点的 pass 计数加一。最后将最后一个字符对应的节点的 end 计数加一。
search(String word): 在 Trie 树中查找一个单词。首先将单词转换为字符数组,然后遍历字符数组,逐个字符在 Trie 树中查找对应的节点。如果找不到某个字符对应的节点,说明该单词不存在于 Trie 树中,返回 0。否则继续查找下一个字符。最后返回最后一个字符对应的节点的 end 计数。
prefixNumber(String pre): 计算 Trie 树中以给定前缀开头的单词数量。首先将前缀转换为字符数组,然后遍历字符数组,逐个字符在 Trie 树中查找对应的节点。如果找不到某个字符对应的节点,说明没有以该前缀开头的单词,返回 0。否则继续查找下一个字符。最后返回最后一个字符对应的节点的 pass 计数。
delete(String word): 从 Trie 树中删除一个单词。首先检查该单词是否存在于 Trie 树中,如果存在,则按照插入的顺序逆序遍历字符数组,逐个字符在 Trie 树中删除对应的节点。每删除一个节点,就将该节点的 pass 计数减一。如果某个节点的 pass 计数变为 0,说明该节点不再被任何单词使用,可以将其删除。最后将最后一个字符对应的节点的 end 计数减一。
public class test5 {public static class Node1{public int pass;public int end;public Node1[] nexts;public Node1(){pass = 0;end = 0;nexts = new Node1[26];}}public static  class Triel{private Node1 root;public Triel(){root = new Node1();}public void insert(String word){if(word == null){return;}char[] str = word.toCharArray();Node1 node = root;node.pass++;int path = 0;for (int i = 0; i < str.length; i++) {path = str[i] - 'a';if(node.nexts[path] == null){node.nexts[path] = new Node1();}node = node.nexts[path];node.pass++;}node.end++;}public int search(String word){if(word == null){return 0;}char[] chs = word.toCharArray();Node1 node =  root;int index  = 0;for (int i = 0; i < chs.length; i++) {index  = chs[i] - 'a';if(node.nexts[index] == null){return 0;}node = node.nexts[index];}return node.end;}public int prefixNumber(String pre){if(pre == null){return 0;}char[] chs = pre.toCharArray();Node1 node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.pass;}public void delete(String word){if(search(word) != 0){char[] chs = word.toCharArray();Node1 node = root;node.pass--;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if(--node.nexts[index].pass == 0){node.nexts[index] =null;return;}node = node.nexts[index];}node.end--;}}}
}

相关文章:

字典树(前缀树)数组实现(只能查26个单词)

这段代码实现了一个基于 Trie 树的字典树&#xff08;Trie&#xff09;数据结构&#xff0c;用于存储和检索字符串。其中包含以下几个方法. insert(String word): 向 Trie 树中插入一个单词。首先将单词转换为字符数组&#xff0c;然后遍历字符数组&#xff0c;逐个字符在 Trie…...

CTF-pwn-虚拟化-vmmware 前置

文章目录 参考vmware逃逸简介虚拟机和主机通信机制(guest to host)共享内存&#xff08;弃用&#xff09;backdoor机制Message_Send和Message_RecvGuestRPC实例RpcOutSendOneRawWork实例 vmware-rpctool info-get guestinfo.ip各个步骤对应的backdoor操作Open RPC channelSend …...

thinkphp8结合layui2.9 图片上传验证

<?php declare (strict_types 1);namespace app\index\validate;use think\Validate;class Upload extends Validate {/*** 定义验证规则* 格式&#xff1a;字段名 > [规则1,规则2...]** var array*/protected $rule [image > fileExt:jpg,png|fileSize:204800|fi…...

农村污水处理难题:探索低成本高效解决方案

农村污水处理难题&#xff1a;探索低成本高效解决方案 农村污水处理作为国家生态文明建设的重要一环&#xff0c;面临着诸多挑战&#xff0c;尤其是技术落后、管理分散、资源匮乏等问题。物联网技术的引入&#xff0c;为解决这些痛点提供了创新途径&#xff0c;实现了对污水处…...

lightningcss介绍及使用

lightningcss介绍及使用 一款使用 rust 编写的 css 解析器&#xff0c;转换器、及压缩器。 特性 特别快&#xff1a;可以在毫秒级别解析、压缩大量的 css 文件&#xff0c;而且比其他工具的打包结果更小给值添加类型&#xff1a;许多其他css解析器会将值解析成一个无类型的 …...

HTTP服务的应用

1、编辑json请求参数&#xff1b; 2、把json发送到服务url&#xff0c;接收服务的返回参数&#xff1b; 3、解析返回参数。 procedure TfrmCustomQuery.btnFullUpdateClick(Sender: TObject); varfrm: TfrmInputQueryConditionEX;b_OK: Boolean;sBeginDate, sEndDate, sJSON…...

uni-app:踩坑路---scroll-view内使用fixed定位,无效的问题

前言&#xff1a; emmm&#xff0c;说起来这个问题整得还挺好笑的&#xff0c;本人在公司内&#xff0c;奋笔疾书写代码&#xff0c;愉快的提交测试的时候&#xff0c;测试跟我说&#xff0c;在苹果手机上你这个样式有bug&#xff0c;我倒是要看看&#xff0c;是什么bug。 安卓…...

MySQL4.索引及视图

1.建库 create database mydb15_indexstu; use mydb15_indexstu;2.建表 2.1 student表学&#xff08;sno&#xff09;号为主键&#xff0c;姓名&#xff08;sname&#xff09;不能重名&#xff0c;性别&#xff08;ssex&#xff09;仅能输入男或女&#xff0c;默认所在系别&a…...

MongoDB - 聚合阶段 $match、$sort、$limit

文章目录 1. $match 聚合阶段1. 构造测试数据2. $match 示例3. $match 示例 2. $sort 聚合阶段1. 排序一致性问题2. $sort 示例 3. $limit 聚合阶段 1. $match 聚合阶段 $match 接受一个指定查询条件的文档。 $match 阶段语法&#xff1a; { $match: { <query> } }$ma…...

ModuleNotFoundError: No module named ‘scrapy.utils.reqser‘

在scrapy中使用scrapy-rabbitmq-scheduler会出现报错 ModuleNotFoundError: No module named scrapy.utils.reqser原因是新的版本的scrapy已经摒弃了该方法,但是scrapy-rabbitmq-scheduler 没有及时的更新,所以此时有两种解决方法 方法一.将scrapy回退至旧版本,找到对应的旧版…...

vue3+ts+vite+electron+electron-packager打包成exe文件

目录 1、创建vite项目 2、添加需求文件 3、根据package.json文件安装依赖 4、打包 5、electron命令运行 6、electron-packager打包成exe文件 Build cross-platform desktop apps with JavaScript, HTML, and CSS | Electron 1、创建vite项目 npm create vitelatest 2、添…...

使用脚本搭建MySQL数据库基础环境

数据库的基本概念 数据&#xff08;Data&#xff09; 描述事物的符号记录 包括数字&#xff0c;文字&#xff0c;图形。图像&#xff0c;声音&#xff0c;档案记录等。 以记录形式按统一格式进行存储 表 将不同的记录组织在一起 用来储存具体数据 数据库 表的集合&#xff0c;是…...

Parameter index out of range (2 > number of parameters, which is 1【已解决】

文章目录 1、SysLogMapper.xml添加注释导致的2、解决方法3、总结 1、SysLogMapper.xml添加注释导致的 <!--定义一个查询方法&#xff0c;用于获取日志列表--><!--方法ID为getLogList&#xff0c;返回类型com.main.server.api.model.SysLogModel,参数类型为com.main.se…...

rk3588s 定制版 USB adb , USB2.0与USB3.0 区别,adb 由typeC 转换到USB3.0(第二部分)

硬件资源&#xff1a; rk3588s 核心板定制的地板 软件资源&#xff1a; 网盘上的 android12 源码 1 硬件上 客户只想使用 type c 接口中的 usb2.0 OTG 。在硬件上&#xff0c;甚至连 CC芯片都没有连接。 关于一些前置的知识。 1 USB2.0 与 USB3.0 的区别。 usb3.0 兼容2.0 …...

Cookie与Session 实现登录操作

Cookie Cookie 是网络编程中使用最广泛的一项技术&#xff0c;主要用于辨识用户身份。 客户端&#xff08;浏览器&#xff09;与网站服务端通讯的过程如下图所示&#xff1a; 从图中看&#xff0c;服务端既要返回 Cookie 给客户端&#xff0c;也要读取客户端提交的 Cookie。所…...

通过IEC104转MQTT网关轻松接入阿里云平台

随着智能电网和物联网技术的飞速发展&#xff0c;电力系统中的传统IEC 104协议设备正面临向现代化、智能化转型的迫切需求。阿里云作为全球领先的云计算服务提供商&#xff0c;其强大的物联网平台为IEC 104设备的接入与数据处理提供了强大的支持。本文将深入探讨钡铼网关在MQTT…...

lua 游戏架构 之 游戏 AI (五)ai_autofight_find_way

这段Lua脚本定义了一个名为 ai_autofight_find_way 的类&#xff0c;继承自 ai_base 类。 lua 游戏架构 之 游戏 AI &#xff08;一&#xff09;ai_base-CSDN博客文章浏览阅读238次。定义了一套接口和属性&#xff0c;可以基于这个基础类派生出具有特定行为的AI组件。例如&…...

vue3+openLayers点击标记事件

<template><!--地图--><div class"distributeMap" id"distributeMap"></div> </template> <script lang"ts" setup> import { onMounted, reactive } from "vue"; import { Feature, Map, View }…...

深入分析 Android ContentProvider (三)

文章目录 深入分析 Android ContentProvider (三)ContentProvider 的高级使用和性能优化1. 高级使用场景1.1. 数据分页加载示例&#xff1a;分页加载 1.2. 使用 Loader 实现异步加载示例&#xff1a;使用 CursorLoader 加载数据 1.3. ContentProvider 与权限管理示例&#xff1…...

养宠浮毛异味双困扰?性价比高的宠物空气净化器推荐

家里养了两只银渐层&#xff0c;谁懂啊&#xff01;一下班打开家门就看到家里飘满了猫浮毛雪&#xff0c;空气中还传来隐隐约约的异味。每天不是在吸毛的路上&#xff0c;就是在洗猫砂盆的路上&#xff0c;而且空气中的浮毛还很难清理干净&#xff0c;这是最让人头疼的问题。 …...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...