当前位置: 首页 > news >正文

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;}
}

image-20240213102700642


前缀树+优先队列

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

image-20240213125607217

复杂度分析:时间复杂度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;}}

image-20240213125625106


资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 时间:2024.2.13

相关文章:

LeetCode、1268. 搜索推荐系统【中等,前缀树+优先队列、排序+前缀匹配】

文章目录 前言LeetCode、1268. 搜索推荐系统【中等&#xff0c;前缀树优先队列、排序前缀匹配】题目类型及分类思路API调用&#xff08;排序前缀匹配&#xff09;前缀树优先队列 资料获取 前言 博主介绍&#xff1a;✌目前全网粉丝2W&#xff0c;csdn博客专家、Java领域优质创…...

计算机视觉基础:矩阵运算

矩阵及其表示方式 一个矩阵是由行(row)和列(column)组成的一个矩形数组&#xff0c;通常包含数字。我们可以用大写字母&#xff08;如 A、B&#xff09;来表示一个矩阵。例如&#xff0c;矩阵 A 可能看起来像这样&#xff1a; A [ a11 a12 a13 ][ a21 a22 a23 ][ a31 a32 a3…...

Gateway中Spring Security6统一处理CORS

文章目录 一、起因二、解决方法 一、起因 使用了gateway微服务作为整体的网关&#xff0c;并且整合了Spring Security6&#xff1b;还有一个system微服务&#xff0c;作为被请求的资源&#xff0c;当浏览器向gateway发送请求&#xff0c;请求system资源时&#xff0c;遇到CORS…...

突破编程_C++_基础教程(输入、输出与文件)

1 流和缓冲区 C中&#xff0c;流&#xff08; stream &#xff09;和缓冲区&#xff08; buffer &#xff09;是两个紧密相关的概念&#xff0c;它们在处理输入和输出时起着重要的作用。 流&#xff08; Stream &#xff09; 流是一种抽象的概念&#xff0c;用于表示数据的流动…...

UE的 HUD 类中的必备方法和属性

在屏幕上绘制的方法 1. DrawText() DrawText() 方法允许开发者在屏幕上渲染文本。参数包括文本内容、位置、颜色、字体、缩放等。 void DrawText(const FString& Text, const FLinearColor& TextColor, float ScreenX, float ScreenY, UFont* Font, float Scale 1.…...

单片机的认识

单片机的定义 先简单理解为&#xff1a; 在一片集成电路芯片上集成了微处理器&#xff08;CPU &#xff09;存储器&#xff08;ROM和RAM&#xff09;、I/O 接口电路&#xff0c;构成单芯片微型计算机&#xff0c;即为单片机。 把组成微型计算机的控制器、运算器、存储器、输…...

转发:udig安装 用来为geoserver上shp地图配置显示样式 颜色

下载udig&#xff0c;解压缩 这东东是基于eclipse的&#xff0c;需要Java JRE 把 JDK 1.8 里面的jre目录拷贝到 udig目录下面 udig下载、安装及汉化&#xff0c;简单生成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 -&#xff1a; 返回上一次所在目录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里面写了个项目&#xff0c;找了半天没办法用cmake调试&#xff0c;最后发现是cmake里面的set(CMAKE_BUILD_TYPE Release)导致的&#xff0c;都是release模式了当然不能调试了&#xff1b;改成Debug就行了 参考&#xff1a;https://stackoverflow.com/questions/7549672…...

Servlet JSP-Eclipse安装配置Maven插件

Maven 是一款比较常用的 Java 开发拓展包&#xff0c;它相当于一个全自动 jar 包管理器&#xff0c;会导入用户开发时需要使用的相应 jar 包。使用 Maven 开发 Java 程序&#xff0c;可以极大提升开发者的开发效率。下面我就跟大家介绍一下如何在 Eclipse 里安装和配置 Maven 插…...

os模块

os 模块是 Python 中用于与操作系统进行交互的标准库之一。它提供了许多函数来执行文件和目录操作&#xff0c;管理进程以及与操作系统交互的其他功能。 下面是一些 os 模块中常用的函数和功能&#xff1a; 文件和目录操作&#xff1a; os.getcwd(): 返回当前工作目录的路径。…...

【C语言进阶】深度剖析数据在内存中的存储--上

1. C语言中的数据类型的简单介绍 注&#xff1a;C99标准里面&#xff0c;定义了bool类型变量。这时&#xff0c;只要引入头文件stdbool.h &#xff0c;就能在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数组

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【C语言基础学习】系列文章 第一章 《项目与程序结构》 第二章 《数据类型》 第三章 《运算符》 第四章 《流程控制》 第五章…...

BUGKU-WEB GET

题目描述 没有提示&#xff0c;就一个get&#xff0c;启动场景看看&#xff1a; 解题思路 显然是PHP语言解读分析代码吧写出你的payload 相关工具 略 解题步骤 进入场景分析代码 $what$_GET[what]; echo $what; if($whatflag) echo flag{****};前两句&#xff1a;使用get…...

蓝桥杯每日一题----唯一分解定理

唯一分解定理 1.内容 任何一个大于1的整数n都可以分解成若干个质数的连乘积&#xff0c;如果不计各个质数的顺序&#xff0c;那么这种分解是惟一的&#xff0c;即若n>1&#xff0c;则有 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)。 页面制作的标准语言&#xff1a;HTML。 超文本标记语言 HTML (HyperText Markup Language) 是一种制作万维网页面的标准语言&#xff0c;它消除了不同计算机之间信息交流的障碍&#xff0c…...

sklearn:机器学习 分类特征编码category_encoders

文章目录 category_encoders简介OrdinalEncoder 序列编码OneHotEncoder 独热编码TargetEncoder 目标编码Binary Encoder 二进制编码BaseNEncoder 贝叶斯编码LeaveOneOutEncoder 留一法HashingEncoder 哈希编码CatBoostEncoder catboost目标编码CountEncoder 频率编码WOEEncoder…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...