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…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
