字典树(前缀树)数组实现(只能查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 树的字典树(Trie)数据结构,用于存储和检索字符串。其中包含以下几个方法. insert(String word): 向 Trie 树中插入一个单词。首先将单词转换为字符数组,然后遍历字符数组,逐个字符在 Trie…...
CTF-pwn-虚拟化-vmmware 前置
文章目录 参考vmware逃逸简介虚拟机和主机通信机制(guest to host)共享内存(弃用)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 {/*** 定义验证规则* 格式:字段名 > [规则1,规则2...]** var array*/protected $rule [image > fileExt:jpg,png|fileSize:204800|fi…...
农村污水处理难题:探索低成本高效解决方案
农村污水处理难题:探索低成本高效解决方案 农村污水处理作为国家生态文明建设的重要一环,面临着诸多挑战,尤其是技术落后、管理分散、资源匮乏等问题。物联网技术的引入,为解决这些痛点提供了创新途径,实现了对污水处…...
lightningcss介绍及使用
lightningcss介绍及使用 一款使用 rust 编写的 css 解析器,转换器、及压缩器。 特性 特别快:可以在毫秒级别解析、压缩大量的 css 文件,而且比其他工具的打包结果更小给值添加类型:许多其他css解析器会将值解析成一个无类型的 …...
HTTP服务的应用
1、编辑json请求参数; 2、把json发送到服务url,接收服务的返回参数; 3、解析返回参数。 procedure TfrmCustomQuery.btnFullUpdateClick(Sender: TObject); varfrm: TfrmInputQueryConditionEX;b_OK: Boolean;sBeginDate, sEndDate, sJSON…...
uni-app:踩坑路---scroll-view内使用fixed定位,无效的问题
前言: emmm,说起来这个问题整得还挺好笑的,本人在公司内,奋笔疾书写代码,愉快的提交测试的时候,测试跟我说,在苹果手机上你这个样式有bug,我倒是要看看,是什么bug。 安卓…...
MySQL4.索引及视图
1.建库 create database mydb15_indexstu; use mydb15_indexstu;2.建表 2.1 student表学(sno)号为主键,姓名(sname)不能重名,性别(ssex)仅能输入男或女,默认所在系别&a…...
MongoDB - 聚合阶段 $match、$sort、$limit
文章目录 1. $match 聚合阶段1. 构造测试数据2. $match 示例3. $match 示例 2. $sort 聚合阶段1. 排序一致性问题2. $sort 示例 3. $limit 聚合阶段 1. $match 聚合阶段 $match 接受一个指定查询条件的文档。 $match 阶段语法: { $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数据库基础环境
数据库的基本概念 数据(Data) 描述事物的符号记录 包括数字,文字,图形。图像,声音,档案记录等。 以记录形式按统一格式进行存储 表 将不同的记录组织在一起 用来储存具体数据 数据库 表的集合,是…...
Parameter index out of range (2 > number of parameters, which is 1【已解决】
文章目录 1、SysLogMapper.xml添加注释导致的2、解决方法3、总结 1、SysLogMapper.xml添加注释导致的 <!--定义一个查询方法,用于获取日志列表--><!--方法ID为getLogList,返回类型com.main.server.api.model.SysLogModel,参数类型为com.main.se…...
rk3588s 定制版 USB adb , USB2.0与USB3.0 区别,adb 由typeC 转换到USB3.0(第二部分)
硬件资源: rk3588s 核心板定制的地板 软件资源: 网盘上的 android12 源码 1 硬件上 客户只想使用 type c 接口中的 usb2.0 OTG 。在硬件上,甚至连 CC芯片都没有连接。 关于一些前置的知识。 1 USB2.0 与 USB3.0 的区别。 usb3.0 兼容2.0 …...
Cookie与Session 实现登录操作
Cookie Cookie 是网络编程中使用最广泛的一项技术,主要用于辨识用户身份。 客户端(浏览器)与网站服务端通讯的过程如下图所示: 从图中看,服务端既要返回 Cookie 给客户端,也要读取客户端提交的 Cookie。所…...
通过IEC104转MQTT网关轻松接入阿里云平台
随着智能电网和物联网技术的飞速发展,电力系统中的传统IEC 104协议设备正面临向现代化、智能化转型的迫切需求。阿里云作为全球领先的云计算服务提供商,其强大的物联网平台为IEC 104设备的接入与数据处理提供了强大的支持。本文将深入探讨钡铼网关在MQTT…...
lua 游戏架构 之 游戏 AI (五)ai_autofight_find_way
这段Lua脚本定义了一个名为 ai_autofight_find_way 的类,继承自 ai_base 类。 lua 游戏架构 之 游戏 AI (一)ai_base-CSDN博客文章浏览阅读238次。定义了一套接口和属性,可以基于这个基础类派生出具有特定行为的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. 数据分页加载示例:分页加载 1.2. 使用 Loader 实现异步加载示例:使用 CursorLoader 加载数据 1.3. ContentProvider 与权限管理示例࿱…...
养宠浮毛异味双困扰?性价比高的宠物空气净化器推荐
家里养了两只银渐层,谁懂啊!一下班打开家门就看到家里飘满了猫浮毛雪,空气中还传来隐隐约约的异味。每天不是在吸毛的路上,就是在洗猫砂盆的路上,而且空气中的浮毛还很难清理干净,这是最让人头疼的问题。 …...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
简单介绍C++中 string与wstring
在C中,string和wstring是两种用于处理不同字符编码的字符串类型,分别基于char和wchar_t字符类型。以下是它们的详细说明和对比: 1. 基础定义 string 类型:std::string 字符类型:char(通常为8位)…...
【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器
从本章节开始,进入到函数有多个参数的情况,前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参,ECX是整型的第一个参数的寄存器,那么多个参数的情况下函数如何传参,下面展开介绍参数为整型时候的几种情…...
ABAP设计模式之---“Tell, Don’t Ask原则”
“Tell, Don’t Ask”是一种重要的面向对象编程设计原则,它强调的是对象之间如何有效地交流和协作。 1. 什么是 Tell, Don’t Ask 原则? 这个原则的核心思想是: “告诉一个对象该做什么,而不是询问一个对象的状态再对它作出决策。…...
