字典树(前缀树)数组实现(只能查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 与权限管理示例࿱…...
养宠浮毛异味双困扰?性价比高的宠物空气净化器推荐
家里养了两只银渐层,谁懂啊!一下班打开家门就看到家里飘满了猫浮毛雪,空气中还传来隐隐约约的异味。每天不是在吸毛的路上,就是在洗猫砂盆的路上,而且空气中的浮毛还很难清理干净,这是最让人头疼的问题。 …...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
