个人建网站的详细步骤,网站空间期限查询,金昌做网站,深圳市布尔工业设计有限公司文章目录1. 题目2. 解题1. 题目
为搜索引擎设计一个搜索自动补全系统。 用户会输入一条语句#xff08;最少包含一个字母#xff0c;以特殊字符 ‘#’ 结尾#xff09;。 除 ‘#’ 以外用户输入的每个字符#xff0c;返回历史中热度前三并以当前输入部分为前缀的句子。下面…
文章目录1. 题目2. 解题1. 题目
为搜索引擎设计一个搜索自动补全系统。 用户会输入一条语句最少包含一个字母以特殊字符 ‘#’ 结尾。 除 ‘#’ 以外用户输入的每个字符返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则
一条句子的热度定义为历史上用户输入这个句子的总次数。返回前三的句子需要按照热度从高到低排序第一个是最热门的。如果有多条热度相同的句子请按照 ASCII 码的顺序输出ASCII 码越小排名越前。如果满足条件的句子个数少于 3将它们全部输出。如果输入了特殊字符意味着句子结束了请返回一个空集合。
你的工作是实现以下功能
构造函数
AutocompleteSystem(String[] sentences, int[] times): 这是构造函数输入的是历史数据。 Sentences 是之前输入过的所有句子Times 是每条句子输入的次数你的系统需要记录这些历史信息。
现在用户输入一条新的句子下面的函数会提供用户输入的下一个字符
ListString input(char c): 其中 c 是用户输入的下一个字符。 字符只会是小写英文字母‘a’ 到 ‘z’ 空格 和特殊字符#。输出历史热度前三的具有相同前缀的句子。
样例
操作 AutocompleteSystem([i love you,
island,ironman, i love leetcode],
[5,3,2,2])
系统记录下所有的句子和出现的次数
i love you : 5 次
island : 3 次
ironman : 2 次
i love leetcode : 2 次
现在用户开始新的键入输入 input(i)
输出 [i love you, island,i love leetcode]
解释
有四个句子含有前缀 i。其中 ironman
和 i love leetcode 有相同的热度
由于 的 ASCII 码是 32 而 r 的 ASCII 码是 114
所以 i love leetcode 在 ironman 前面。
同时我们只输出前三的句子所以 ironman 被舍弃。输入 input( )
输出 [i love you,i love leetcode]
解释:
只有两个句子含有前缀 i 。输入 input(a)
输出 []
解释
没有句子有前缀 i a。输入 input(#)
输出 []
解释 用户输入结束i a 被存到系统中后面的输入被认为是下一次搜索。注释 输入的句子以字母开头以 ‘#’ 结尾两个字母之间最多只会出现一个空格。 即将搜索的句子总数不会超过 100。 每条句子的长度包括已经搜索的和即将搜索的也不会超过 100。 即使只有一个字母输出的时候请使用双引号而不是单引号。 请记住清零 AutocompleteSystem 类中的变量因为静态变量、类变量会在多组测试数据中保存之前结果。详情请看这里。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/design-search-autocomplete-system 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class trie
{
public:unordered_mapchar, trie* next;string word;//记录单词int freq 0;//是单词时记录频数void insert(string s, int time){trie *cur this;for(int i 0; i s.size(); i){if(!cur-next.count(s[i]))cur-next[s[i]] new trie();cur cur-next[s[i]];}cur-word s;cur-freq time;}void find(trie* cur, vectorpairint, string freq_wd){if(!cur) return;if(cur-freq)//找到单词存入候选集合freq_wd.push_back({cur-freq, cur-word});for(auto item : cur-next)find(item.second, freq_wd);}
};
class AutocompleteSystem {trie* t, *cur;string prefix;
public:AutocompleteSystem(vectorstring sentences, vectorint times) {t new trie();cur t;for(int i 0; i sentences.size(); i)t-insert(sentences[i], times[i]);}vectorstring input(char c) {if(c #){t-insert(prefix, 1);//单词记录1次prefix ;cur t;return {};}else{prefix c;if(!cur-next.count(c))cur-next[c] new trie();cur cur-next[c];vectorpairint, string freq_wd;t-find(cur, freq_wd);sort(freq_wd.begin(), freq_wd.end(),[](auto a, auto b){if(a.first b.first)return a.second b.second;return a.first b.first;});//排序取前3vectorstring ans;for(int i 0; i min(3, int(freq_wd.size())); i)ans.push_back(freq_wd[i].second);return ans;}}
};1040 ms 238.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
