当前位置: 首页 > 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;这是最让人头疼的问题。 …...

保姆级教程:用Cloudreve+Obsidian打造私人云笔记(附WebDAV配置避坑指南)

零基础构建私有知识库&#xff1a;Cloudreve与Obsidian的完美联姻 在信息爆炸的时代&#xff0c;如何高效管理个人知识资产已成为现代人的刚需。想象一下&#xff1a;你正在咖啡馆用iPad记录灵感&#xff0c;回到家打开电脑时这些想法已自动同步&#xff1b;出差途中用手机查阅…...

开源动作捕捉与3D数据采集:FreeMoCap如何颠覆传统动捕方案

开源动作捕捉与3D数据采集&#xff1a;FreeMoCap如何颠覆传统动捕方案 【免费下载链接】freemocap Free Motion Capture for Everyone &#x1f480;✨ 项目地址: https://gitcode.com/GitHub_Trending/fr/freemocap 在游戏开发、动画制作和运动科学研究领域&#xff0c…...

UModel:虚幻引擎资源解析工具零基础入门到高级应用指南

UModel&#xff1a;虚幻引擎资源解析工具零基础入门到高级应用指南 【免费下载链接】UEViewer Viewer and exporter for Unreal Engine 1-4 assets (UE Viewer). 项目地址: https://gitcode.com/gh_mirrors/ue/UEViewer 虚幻引擎资源解析是游戏开发与逆向工程领域的关键…...

OpenClaw多模型切换技巧:GLM-4.7-Flash与Qwen3-32B混合调用实战

OpenClaw多模型切换技巧&#xff1a;GLM-4.7-Flash与Qwen3-32B混合调用实战 1. 为什么需要多模型切换 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动处理周报时&#xff0c;发现一个有趣的现象&#xff1a;用同一个模型处理文本摘要和代码片段时&#xff0c;效果差异很大…...

当NB-IoT遇上同步轨道卫星:GEO场景下的定时关系增强全指南(基于3GPP Release 17最新规范)

GEO卫星场景下NB-IoT定时关系增强技术解析 1. GEO卫星通信与NB-IoT的技术融合挑战 地球静止轨道&#xff08;GEO&#xff09;卫星通信与窄带物联网&#xff08;NB-IoT&#xff09;技术的结合&#xff0c;为全球物联网覆盖提供了革命性解决方案。GEO卫星位于地球赤道上空35,786公…...

ESP8266-ESP32 物联网开发入门

ESP8266/ESP32物联网开发入门指南 在智能家居、远程监控和工业自动化等领域&#xff0c;物联网技术正快速改变我们的生活。作为物联网开发的热门选择&#xff0c;ESP8266和ESP32凭借低成本、高性能和丰富的开发资源&#xff0c;成为初学者和工程师的首选。本文将介绍如何快速入…...

vLLM-v0.17.1参数详解:--enforce-eager --disable-custom-all-reduce说明

vLLM-v0.17.1参数详解&#xff1a;--enforce-eager --disable-custom-all-reduce说明 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;以其出色的吞吐量和易用性著称。这个项目最初由加州大学伯克利分校的天空计算实验室开发&#xff…...

解码 DINO 核心:三大创新如何重塑端到端目标检测

1. 从DETR到DINO&#xff1a;目标检测的范式革命 记得我第一次用Faster R-CNN做目标检测时&#xff0c;光是调整锚框尺寸就花了整整三天。这种传统检测方法就像用老式打字机写代码——每个环节都需要手工微调。直到2020年DETR横空出世&#xff0c;才让我意识到目标检测还能这么…...

如何将Uvicorn部署到Azure Functions Premium Plan:完整指南

如何将Uvicorn部署到Azure Functions Premium Plan&#xff1a;完整指南 【免费下载链接】uvicorn An ASGI web server, for Python. &#x1f984; 项目地址: https://gitcode.com/GitHub_Trending/uv/uvicorn Uvicorn是Python生态中备受推崇的ASGI Web服务器&#xff…...

基于MATLAB的VSG逆变器无源性分析与稳定性研究

基于MATLAB的VSG逆变器无源性分析与稳定性研究 摘要 随着分布式发电和微电网技术的快速发展,逆变器作为新能源并网的关键接口,其稳定性问题日益突出。虚拟同步发电机(VSG)控制技术通过模拟同步发电机的机电特性,为逆变器提供惯性和阻尼支撑,成为提升系统稳定性的重要手…...