当前位置:网站首页>【面试高频题】难度 2.5/5,简单结合 DFS 的 Trie 模板级运用题
【面试高频题】难度 2.5/5,简单结合 DFS 的 Trie 模板级运用题
2022-07-07 11:31:00 【宫水三叶的刷题日记】
题目描述
这是 LeetCode 上的 「677. 键值映射」 ,难度为 「中等」。
Tag : 「字典树」、「DFS」、「哈希表」
实现一个 MapSum
类,支持两个方法,insert
和 sum
:
MapSum()
初始化MapSum
对象void insert(String key, int val)
插入key-val
键值对,字符串表示键key
,整数表示值val
。如果键key
已经存在,那么原来的键值对将被替代成新的键值对。int sum(string prefix)
返回所有以该前缀prefix
开头的键key
的值的总和。
示例:
输入:
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出:
[null, null, 3, null, 5]
解释:
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
提示:
key
和prefix
仅由小写英文字母组成1 <= val <= 1000
最多调用 50
次insert
和sum
Trie + DFS
从需要实现「存储字符串(映射关系)」并「检索某个字符串前缀的总和」来看,可以知道这是与 相关的题目,还不了解 的同学可以先看前置 :实现 Trie (前缀树) 。
考虑如何实现两个操作:
insert
:在基本的 插入操作的基础上进行拓展即可。与常规的插入操作的唯一区别为,不能简单记录单词的结束位置,还要存储 对应的 是多少。具体的我们可以使用int
类型的数组 来代替原有的boolean
类型的数组 ;sum
: 先对入参 进行字典树搜索,到达尾部后再使用DFS
搜索后面的所有方案,并累加结果。
代码(static
优化代码见 ,避免每个样例都 new
大数组):
class MapSum {
int[][] tr = new int[2510][26];
int[] hash = new int[2510];
int idx;
public void insert(String key, int val) {
int p = 0;
for (int i = 0; i < key.length(); i++) {
int u = key.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
hash[p] = val;
}
public int sum(String prefix) {
int p = 0;
for (int i = 0; i < prefix.length(); i++) {
int u = prefix.charAt(i) - 'a';
if (tr[p][u] == 0) return 0;
p = tr[p][u];
}
return dfs(p);
}
int dfs(int p) {
int ans = hash[p];
for (int u = 0; u < 26; u++) {
if (tr[p][u] != 0) ans += dfs(tr[p][u]);
}
return ans;
}
}
class MapSum {
static int[][] tr = new int[2510][26];
static int[] hash = new int[2510];
static int idx;
public MapSum() {
for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
Arrays.fill(hash, 0);
idx = 0;
}
public void insert(String key, int val) {
int p = 0;
for (int i = 0; i < key.length(); i++) {
int u = key.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
hash[p] = val;
}
public int sum(String prefix) {
int p = 0;
for (int i = 0; i < prefix.length(); i++) {
int u = prefix.charAt(i) - 'a';
if (tr[p][u] == 0) return 0;
p = tr[p][u];
}
return dfs(p);
}
int dfs(int p) {
int ans = hash[p];
for (int u = 0; u < 26; u++) {
if (tr[p][u] != 0) ans += dfs(tr[p][u]);
}
return ans;
}
}
时间复杂度:令 的最大长度为 ,最大调用次数为 ,字符集大小为 ( 本题 固定为 ), insert
操作的复杂度为 ;从DFS
的角度分析,sum
操作的复杂度为 ,但事实上,对于本题具有明确的计算量上界,搜索所有的格子的复杂度为空间复杂度:
Trie 记录前缀字符串总和
为降低 sum
操作的复杂度,我们可以在 insert
操作中同时记录(累加)每个前缀的总和。
代码(static
优化代码见 ,避免每个样例都 new
大数组):
class MapSum {
int N = 2510;
int[][] tr = new int[N][26];
int[] hash = new int[N];
int idx;
Map<String, Integer> map = new HashMap<>();
public void insert(String key, int val) {
int _val = val;
if (map.containsKey(key)) val -= map.get(key);
map.put(key, _val);
for (int i = 0, p = 0; i < key.length(); i++) {
int u = key.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
hash[p] += val;
}
}
public int sum(String prefix) {
int p = 0;
for (int i = 0; i < prefix.length(); i++) {
int u = prefix.charAt(i) - 'a';
if (tr[p][u] == 0) return 0;
p = tr[p][u];
}
return hash[p];
}
}
class MapSum {
static int N = 2510;
static int[][] tr = new int[N][26];
static int[] hash = new int[N];
static int idx;
static Map<String, Integer> map = new HashMap<>();
public MapSum() {
for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
Arrays.fill(hash, 0);
idx = 0;
map.clear();
}
public void insert(String key, int val) {
int _val = val;
if (map.containsKey(key)) val -= map.get(key);
map.put(key, _val);
for (int i = 0, p = 0; i < key.length(); i++) {
int u = key.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
hash[p] += val;
}
}
public int sum(String prefix) {
int p = 0;
for (int i = 0; i < prefix.length(); i++) {
int u = prefix.charAt(i) - 'a';
if (tr[p][u] == 0) return 0;
p = tr[p][u];
}
return hash[p];
}
}
时间复杂度:令 的最大长度为 , insert
操作的复杂度为 ;sum
操作的复杂度为空间复杂度:令 的最大长度为 ,最大调用次数为 ,字符集大小为 ( 本题 固定为 ),复杂度为
最后
这是我们「刷穿 LeetCode」系列文章的第 No.677
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
边栏推荐
- [1] ROS2基础知识-操作命令总结版
- 抓细抓实抓好安全生产各项工作 全力确保人民群众生命财产安全
- [learning notes] agc010
- 存储过程的介绍与基本使用
- Realbasicvsr test pictures and videos
- Cinnamon Applet 入门
- Japanese government and enterprise employees got drunk and lost 460000 information USB flash drives. They publicly apologized and disclosed password rules
- MATLAB中polarscatter函数使用
- Isprs2021/ remote sensing image cloud detection: a geographic information driven method and a new large-scale remote sensing cloud / snow detection data set
- Milkdown control icon
猜你喜欢
10 pictures open the door of CPU cache consistency
Introduction and basic use of stored procedures
将数学公式在el-table里面展示出来
error LNK2019: 无法解析的外部符号
Practical example of propeller easydl: automatic scratch recognition of industrial parts
Centso7 OpenSSL error Verify return code: 20 (unable to get local issuer certificate)
Ways to improve the performance of raspberry pie
【Presto Profile系列】Timeline使用
Use of polarscatter function in MATLAB
LED light of single chip microcomputer learning notes
随机推荐
shell 批量文件名(不含扩展名)小写改大写
Milkdown 控件图标
About the problem of APP flash back after appium starts the app - (solved)
[untitled]
学习突围2 - 关于高效学习的方法
Cinnamon taskbar speed
Ogre introduction
自定义线程池拒绝策略
php——laravel缓存cache
MongoDB的导入导出、备份恢复总结
MATLAB中polarscatter函数使用
Some principles of mongodb optimization
Write it down once Net a new energy system thread surge analysis
Unity build error: the name "editorutility" does not exist in the current context
Ogre入门尝鲜
[untitled]
JS中为什么基础数据类型可以调用方法
ESP32 ① 编译环境
Storage principle inside mongodb
About how appium closes apps (resolved)