LeetCode、1268. 搜索推荐系统【中等,前缀树+优先队列、排序+前缀匹配】
文章目录
- 前言
- LeetCode、1268. 搜索推荐系统【中等,前缀树+优先队列、排序+前缀匹配】
- 题目类型及分类
- 思路
- API调用(排序+前缀匹配)
- 前缀树+优先队列
- 资料获取
前言
博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引:博客目录索引(持续更新)
视频平台:b站-Coder长路
LeetCode、1268. 搜索推荐系统【中等,前缀树+优先队列、排序+前缀匹配】
题目类型及分类
题目链接:LeetCode、1268. 搜索推荐系统
分类:02数据结构/树/字典树(前缀树)
思路
API调用(排序+前缀匹配)
复杂度分析:时间复杂度O(n.logn);空间复杂度O(n)
class Solution {//prodcuts数量2万 单词1000public List<List<String>> suggestedProducts(String[] products, String searchWord) {//根据字典序排序Arrays.sort(products);//初始化结果集合List<List<String>> ans = new ArrayList<>();//遍历所有的搜索文字for (int i = 0; i < searchWord.length(); i ++) {String s = searchWord.substring(0, i + 1);//结果集合List<String> res = new ArrayList<>();//遍历所有productsfor (String product: products) {if (product.startsWith(s)) {res.add(product);}//若是已经收集到3个if (res.size() == 3) {break;}}ans.add(res);}return ans;}
}

前缀树+优先队列
使用大顶堆目的:每个单词只留下3个最小字典序的,因为一旦大顶堆中有>目标数量时,就会将最大的排除出去。

复杂度分析:时间复杂度O(n);空间复杂度O(n)
class Solution {//每一个大顶堆中的数量为3private static final int size = 3;//根节点private TrieNode root = new TrieNode();//自定义Node节点class TrieNode {public static final int num = 26;TrieNode[] children;boolean isEnd;PriorityQueue<String> queue;public TrieNode() {this.children = new TrieNode[num];this.queue = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));}}//插入一个产品名称到前缀树public void insert(String product) {//拿到当前的前缀树节点TrieNode node = this.root;//遍历整个名称字符for (char ch: product.toCharArray()) {int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new TrieNode();}node = node.children[index];//当前节点要将单词添加进来node.queue.offer(product);if (node.queue.size() > size) {node.queue.poll();}}node.isEnd = true;}public List<List<String>> suggestedProducts(String[] products, String searchWord) {List<List<String>> ans = new ArrayList<>();//遍历所有的商品名称,依次添加到前缀树中for (String product: products) {insert(product);}//搜索所有的匹配结果TrieNode node = this.root;for (char ch: searchWord.toCharArray()) {int index = ch - 'a';//临时保存一个集合List<String> tmp = new ArrayList<>(); if (node == null) {ans.add(tmp);continue;}node = node.children[index];//节点不为空情况while (node != null && !node.queue.isEmpty()) {tmp.add(node.queue.poll());}//将整个集合翻转Collections.reverse(tmp);//添加到最终的结果集合中ans.add(tmp);}return ans;}}

资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅:在下方专栏👇🏻
- 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
- 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
- 学习与生活-专栏:可以了解博主的学习历程
- 算法专栏:算法收录
更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅
整理者:长路 时间:2024.2.13
相关文章:
LeetCode、1268. 搜索推荐系统【中等,前缀树+优先队列、排序+前缀匹配】
文章目录 前言LeetCode、1268. 搜索推荐系统【中等,前缀树优先队列、排序前缀匹配】题目类型及分类思路API调用(排序前缀匹配)前缀树优先队列 资料获取 前言 博主介绍:✌目前全网粉丝2W,csdn博客专家、Java领域优质创…...
计算机视觉基础:矩阵运算
矩阵及其表示方式 一个矩阵是由行(row)和列(column)组成的一个矩形数组,通常包含数字。我们可以用大写字母(如 A、B)来表示一个矩阵。例如,矩阵 A 可能看起来像这样: A [ a11 a12 a13 ][ a21 a22 a23 ][ a31 a32 a3…...
Gateway中Spring Security6统一处理CORS
文章目录 一、起因二、解决方法 一、起因 使用了gateway微服务作为整体的网关,并且整合了Spring Security6;还有一个system微服务,作为被请求的资源,当浏览器向gateway发送请求,请求system资源时,遇到CORS…...
突破编程_C++_基础教程(输入、输出与文件)
1 流和缓冲区 C中,流( stream )和缓冲区( buffer )是两个紧密相关的概念,它们在处理输入和输出时起着重要的作用。 流( Stream ) 流是一种抽象的概念,用于表示数据的流动…...
UE的 HUD 类中的必备方法和属性
在屏幕上绘制的方法 1. DrawText() DrawText() 方法允许开发者在屏幕上渲染文本。参数包括文本内容、位置、颜色、字体、缩放等。 void DrawText(const FString& Text, const FLinearColor& TextColor, float ScreenX, float ScreenY, UFont* Font, float Scale 1.…...
单片机的认识
单片机的定义 先简单理解为: 在一片集成电路芯片上集成了微处理器(CPU )存储器(ROM和RAM)、I/O 接口电路,构成单芯片微型计算机,即为单片机。 把组成微型计算机的控制器、运算器、存储器、输…...
转发:udig安装 用来为geoserver上shp地图配置显示样式 颜色
下载udig,解压缩 这东东是基于eclipse的,需要Java JRE 把 JDK 1.8 里面的jre目录拷贝到 udig目录下面 udig下载、安装及汉化,简单生成geoserver图层样式sld-CSDN博客...
Linux--常用命令(详解)
详细目录 一、终端命令格式二、显示文件列表命令-ls2.1作用2.2格式2.3 ls常用选项2.3.1 ls -a2.3.2 ls -l(等价于 ll)2.3.2 ls -h 三、相对路径与绝对路径3.1绝对路径3.2相对路径 四、目录操作命令 -cd4.1作用4.2格式4.3案例4.3.1 cd -: 返回上一次所在目录4.3.2 cd…...
SouthLeetCode-打卡24年02月第1周
SouthLeetCode-打卡24年02月第1周 // Date : 2024/02/01 ~ 2024/02/04 034.合并两个有序链表 (1) 题目描述 034#LeetCode.21.#北岸计划2024/02/01 将两个升序链表合并为一个新的 升序 链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 (2) 题解代码 cla…...
vscode的cmake工具小三角符号旁边没有目标的解决方法
vscode里面写了个项目,找了半天没办法用cmake调试,最后发现是cmake里面的set(CMAKE_BUILD_TYPE Release)导致的,都是release模式了当然不能调试了;改成Debug就行了 参考:https://stackoverflow.com/questions/7549672…...
Servlet JSP-Eclipse安装配置Maven插件
Maven 是一款比较常用的 Java 开发拓展包,它相当于一个全自动 jar 包管理器,会导入用户开发时需要使用的相应 jar 包。使用 Maven 开发 Java 程序,可以极大提升开发者的开发效率。下面我就跟大家介绍一下如何在 Eclipse 里安装和配置 Maven 插…...
os模块
os 模块是 Python 中用于与操作系统进行交互的标准库之一。它提供了许多函数来执行文件和目录操作,管理进程以及与操作系统交互的其他功能。 下面是一些 os 模块中常用的函数和功能: 文件和目录操作: os.getcwd(): 返回当前工作目录的路径。…...
【C语言进阶】深度剖析数据在内存中的存储--上
1. C语言中的数据类型的简单介绍 注:C99标准里面,定义了bool类型变量。这时,只要引入头文件stdbool.h ,就能在C语言里面正常使用bool类型。 1.1 在C语言中各类型所占内存空间的大小如下 char类型的数据类型大小为1字节即8比特位。…...
【doghead】VS2022 win11 安装配置WSL2 以编译linux端的cmake项目并运行2
【bifrost】VS2022 win11 安装配置WSL2 以编译linux端的cmake项目并运行1 完成了WSL2的安装。13900K 的电脑安装了ubuntu22.04构建中出现了一些问题,fix了。发现libuv 似乎不识别,认为是libuv.so ,无法让worker识别到uv 从而没构建。干脆单独构建好了,官方的脚本如此:而且…...
【教程】C++语言基础学习笔记(七)——Array数组
写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 【C语言基础学习】系列文章 第一章 《项目与程序结构》 第二章 《数据类型》 第三章 《运算符》 第四章 《流程控制》 第五章…...
BUGKU-WEB GET
题目描述 没有提示,就一个get,启动场景看看: 解题思路 显然是PHP语言解读分析代码吧写出你的payload 相关工具 略 解题步骤 进入场景分析代码 $what$_GET[what]; echo $what; if($whatflag) echo flag{****};前两句:使用get…...
蓝桥杯每日一题----唯一分解定理
唯一分解定理 1.内容 任何一个大于1的整数n都可以分解成若干个质数的连乘积,如果不计各个质数的顺序,那么这种分解是惟一的,即若n>1,则有 n ∏ p i j n\prod{p^j_i} n∏pij 这里的 p i p_i pi是质数。可以进行简单证明…...
openssl3.2 - osslsigncode工程的学习
文章目录 openssl3.2 - osslsigncode工程的学习概述笔记工程库地址工程的编译osslsigncodeM工程文件列表osslsigncodeM工程搭建细节原始工程实现的改动自己封装的包含openssl和curl的实现osslsigncodeM工程命令行的用法备注 - VS2019调试环境备注 - 如果要单步openssl的API学学…...
HTML 超文本标记语言
超文本标记语言 HTML 在一个客户程序主窗口上显示出的万维网文档称为页面 (page)。 页面制作的标准语言:HTML。 超文本标记语言 HTML (HyperText Markup Language) 是一种制作万维网页面的标准语言,它消除了不同计算机之间信息交流的障碍,…...
sklearn:机器学习 分类特征编码category_encoders
文章目录 category_encoders简介OrdinalEncoder 序列编码OneHotEncoder 独热编码TargetEncoder 目标编码Binary Encoder 二进制编码BaseNEncoder 贝叶斯编码LeaveOneOutEncoder 留一法HashingEncoder 哈希编码CatBoostEncoder catboost目标编码CountEncoder 频率编码WOEEncoder…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
