福州什么推广网站好,网络推广商城网站,湖南网站建设磐石网络口碑好,厦门建网站平台文章目录 前言LeetCode、1268. 搜索推荐系统【中等#xff0c;前缀树优先队列、排序前缀匹配】题目类型及分类思路API调用#xff08;排序前缀匹配#xff09;前缀树优先队列 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博客专家、Java领域优质创… 文章目录 前言LeetCode、1268. 搜索推荐系统【中等前缀树优先队列、排序前缀匹配】题目类型及分类思路API调用排序前缀匹配前缀树优先队列 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、1268. 搜索推荐系统【中等前缀树优先队列、排序前缀匹配】
题目类型及分类
题目链接LeetCode、1268. 搜索推荐系统
分类02数据结构/树/字典树(前缀树) 思路
API调用排序前缀匹配
复杂度分析时间复杂度O(n.logn)空间复杂度O(n)
class Solution {//prodcuts数量2万 单词1000public ListListString suggestedProducts(String[] products, String searchWord) {//根据字典序排序Arrays.sort(products);//初始化结果集合ListListString ans new ArrayList();//遍历所有的搜索文字for (int i 0; i searchWord.length(); i ) {String s searchWord.substring(0, i 1);//结果集合ListString 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;PriorityQueueString 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 ListListString suggestedProducts(String[] products, String searchWord) {ListListString ans new ArrayList();//遍历所有的商品名称依次添加到前缀树中for (String product: products) {insert(product);}//搜索所有的匹配结果TrieNode node this.root;for (char ch: searchWord.toCharArray()) {int index ch - a;//临时保存一个集合ListString 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—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取 整理者长路 时间2024.2.13
