【LeetCode】208.实现Trie(前缀树)
题目
Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中,返回true(即,在检索之前已经插入);否则,返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix,返回true;否则,返回false。
示例:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示:
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 10^4次
解答
源代码
class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {return searchPrefix(word) != null && searchPrefix(word).isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/
总结
有些复杂啊……第一次没折腾出来放弃了,第二次才AC了。
官解用的其实相当于一个26叉数,成员变量children数组表示的是下一个字母,0索引对应' a ',25索引对应' z ';isEnd表示当前字母是否为一个单词的末尾。
相关文章:
【LeetCode】208.实现Trie(前缀树)
题目 Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。 请你实现 Trie 类: Trie() 初始化前缀…...
多线程笔记: volatile、synchronized、Monitor等
为什么非volatile变量也有线程可见性?不加volatile也可以看到变量变化是为什么?Thread.sleep() 和 System.out.println() 与内存可见性的影响Thread.sleep() 对线程可见性的影响?Java中的Monitor监视器是什么? Slf4j public clas…...
shell语法--数组相关
shell定义一个数组 在 shell 中,可以使用以下语法来定义一个数组: array_name(item1 item2 item3 ...) 其中,array_name 是数组的名称,item1、item2、item3 等是数组中的元素,它们之间用空格分隔。例如,以下…...
AI:05 - 基于深度学习的道路交通信号灯的检测与识别
随着人工智能的快速发展,基于深度学习的视觉算法在道路交通领域中起到了重要作用。本文将探讨如何利用深度学习技术实现道路交通信号灯的检测与识别,通过多处代码实例展示技术深度。 道路交通信号灯是指示交通参与者行驶和停止的重要信号。准确地检测和识别交通信号灯对于智…...
The Sandbox 即将参加韩国区块链周,并带来一系列独家周边活动!
韩国区块链周(Korea Blockchain Week)即将到来,届时将有成千上万的 NFT 项目、建设者、社区成员、企业家、投资者和爱好者齐聚首尔,分享 Web3 的最新更新和未来愿景。 继成功举办韩流崛起 LAND 销售并宣布多个合作伙伴关系之后&a…...
Mysql高阶语句 (一)
一、常用查询 (增、删、改、查) 对 MySQL 数据库的查询,除了基本的查询外,有时候需要对查询的结果集进行处理。 例如只取 10 条数据、对查询结果进行排序或分组等等 1、按关键字排序 PS:类比于windows 任务管理器 使用 SELECT 语句…...
win10 ping不通 Docker ip(解决截图)
背景: win10下载了docker desktop就是这个图,然后计划做一个springboot连接docker。 docker部署springboot :docker 部署springboot(成功、截图)_總鑽風的博客-CSDN博客 问题:spring boot部署docker后,docker接口通了࿰…...
讲讲几道关于 TCP/UDP 通信的面试题
TCP (1)TCP 的 accept 发生在三次握手的哪个阶段? 如下图connect和accept的关系: accept过程发生在三次握手之后,三次握手完成后,客户端和服务器就建立了tcp连接并可以进行数据交互了。这时可以调用accep…...
golang 连接 oracle 数据库 增删改查
1,golang 连接 oracle 数据库 2,增删改查 /** Author: lmy* Date: 2023-08-24 15:19:22* LastEditors: lmy* LastEditTime: 2023-08-24 16:23:58* FilePath: \golangOracleDemo\main.go* Description: golang oracle 增删改查 DEMO*/package mainimpor…...
Unity——音频管理器(附例子)
在实际游戏开发中,音效既是一个相对独立的部分,又与其他游戏逻辑密切关联。也就是说,与音效相关的代码会插入很多细节代码中。 而且在音效非常丰富的情况下,如果每一个游戏模块都单独播放音效,那么可能会带来一些问题…...
TCP协议基础
一: TCP协议是什么? TCP协议是基于面向连接,可靠传输,基于字节流的传输层通信协议 1. 面向连接 TCP协议是一种面向连接的协议,意味着在双方在建立数据传输之前,需要进行一个逻辑上的连接,且是…...
C# NetTopologySuite+ProjNet 任意图形类型坐标转换
添加引用:NetTopologySuite、ProjNet、ProjNet.SRID Program.cs文件: using ProjNet.CoordinateSystems; using ProjNet.CoordinateSystems.Transformations; using ProjNet.SRID; using System; using System.Collections.Generic; using System.Linq;…...
Windows笔记本电脑开机黑屏
Windows笔记本电脑开机黑屏 最近,我遇到了一件奇怪的事情。我的Windows笔记本电脑在开机时出现了一个黑屏,没有任何反应。我尝试了多种方法,包括重启和恢复出厂设置,但都无济于事。 我开始感到担心,因为这只会影响到…...
Samb共享用户的设置和修改Linux用户的id号,修改Linux组的id号,加入组,删除组成员等
零、samba帐号的设置 为samba共享添加用户,并设定仅能由授权用户进入的共享 #增加没有家目录,也无法登录系统的空用户 useradd -M userA -s /sbin/nologin #-M 选项是--no-create-home的简写形式,即不为该用户配置家目录;-s选项&…...
VBA:对Excel单元格进行合并操作
Sub hb()Dim nn 3For i 3 To 18If Range("b" & i) <> Range("b" & i 1) ThenRange("b" & n & ":b" & i).Mergen i 1End IfNextEnd Sub...
HTML5离线储存
简介 离线存储指的是:在用户没有与因特网连接时,可以正常访问站点或应用,在用户与因特网连接时,更新用户机器上的缓存文件。 原理:HTML5的离线存储是基于一个新建的 .appcache 文件的缓存机制(不是存储技术)…...
cmd: Union[List[str], str], ^ SyntaxError: invalid syntax
跑项目在调用from easyprocess import EasyProcess 遇到报错: cmd: Union[List[str], str], ^ SyntaxError: invalid syntax猜测是EasyProcess版本与python版本不对应 pip show EasyProcess查证一下: WARNING: pip is being invoked by an old…...
2023高教社杯数学建模思路 - 案例:异常检测
文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…...
FFDNet-pytorch版本代码测试教程
一、FFDNet-pytorch版本代码下载 (1)FFDNet-pytorch下载 https://download.csdn.net/download/qq_41104871/88233742 二、FFDNet-pytorch版本代码运行环境配置 (1)FFDNet-pytorch版本代码运行环境配置 https://blog.csdn.net/q…...
uni-app项目由hbuilder项目转化为cli项目
1.背景 原uni-app项目是通过hbuilder创建的,运行以及打包都要依赖于hbuilder运行;一般在vscode开发,在hbuilder运行比较怪异;后续希望脱离hbuilder运行并能通过构建平台进行打包,因此将hbuilder项目转化为cli项目 2.…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
