键值映射
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
* MapSum class implements a map that supports two operations using Java Streams:
* 1. insert(String key, int val): Insert a key-value pair into the map. If the key already exists, update the value.
* 2. sum(String prefix): Return the sum of all values of keys that start with the given prefix.
*/
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
public class MapSum {
private Map<String, Integer> map;
// Constructor to initialize the map
public MapSum() {
map = new HashMap<>();
}
// Insert a key-value pair into the map
public void insert(String key, int val) {
map.put(key, val);
}
// Return the sum of values for all keys starting with the given prefix using Java Streams
public int sum(String prefix) {
return map.entrySet().stream()
.filter(entry -> entry.getKey().startsWith(prefix))
.collect(Collectors.summingInt(Map.Entry::getValue));
}
}
解释
方法:
该题解采用了字典和字典树(Trie)的结合方法。主要包括两个部分:1. 一个普通字典 'map' 存储键值对,用于记录每个键对应的最新值。2. 字典树 'root',其中每个节点存储了到该节点为止的所有键的值的累积和。插入操作时,首先计算当前键值与原始值的差值(delta),然后更新字典树中经过该键的所有节点的累积值。查询前缀和时,遍历字典树直到前缀的末尾,然后返回该节点的累积和。
时间复杂度:
O(k) for insert, O(p) for sum
空间复杂度:
O(N*k)
代码细节讲解
🦆
为什么在插入操作中需要计算当前键值与原始值的差值(delta),而不是直接使用新的键值进行更新?
▷🦆
当插入操作中的键已存在于字典中时,原有的节点在字典树中的累积值是如何被正确调整的?
▷🦆
在查询前缀和的操作中,如果前缀不存在,直接返回0的处理方式是否会影响到其他操作或数据的准确性?
▷🦆
字典树的根节点在每次插入操作时都更新其累积值,这种设计有什么特别的优点或原因?
▷