【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|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
