677. Map Sum Pairs
6
LWC 50：677. Map Sum Pairs
Problem:
Implement a MapSum class with insert, and sum methods. For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one. For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.
Example 1:
Input: insert(“apple”, 3), Output: Null Input: sum(“ap”), Output: 3 Input: insert(“app”, 2), Output: Null Input: sum(“ap”), Output: 5
两种做法，在插入时，记入所有前缀，查询快。第二种做法为插入时直接记录，查询时计算所有前缀， 插入快。
插入O(n)查询O(1)
class MapSum {
/** Initialize your data structure here. */
Map<String, Integer> mem;
Map<String, Integer> set;
public MapSum() {
mem = new HashMap<>();
set = new HashMap<>();
}
public void insert(String key, int val) {
if (!set.containsKey(key)){
set.put(key, val);
for (int i = 0; i <= key.length(); ++i){
String sub = key.substring(0, i);
mem.put(sub,mem.getOrDefault(sub, 0) + val);
}
}else{
int cnt = set.get(key);
for (int i = 0; i <= key.length(); ++i){
String sub = key.substring(0, i);
mem.put(sub, mem.get(sub) - cnt + val);
}
}
}
public int sum(String prefix) {
if (!mem.containsKey(prefix)) return 0;
return mem.get(prefix);
}
}插入O(1)查询O(n)
class MapSum {
/** Initialize your data structure here. */
Map<String, Integer> mem;
public MapSum() {
mem = new HashMap<>();
}
public void insert(String key, int val) {
mem.put(key, val);
}
public int sum(String prefix) {
int sum = 0;
for (String pre : mem.keySet()) {
for (int i = 0; i <= pre.length(); ++i) {
if (prefix.equals(pre.substring(0, i))) {
sum += mem.get(pre);
}
}
}
return sum;
}
}当然你还可以使用Trie来维护前缀，代码如下：
class MapSum {
class TrieNode{
TrieNode[] children = new TrieNode[26];
int val;
}
TrieNode build(TrieNode root, String key, int val) {
char[] cs = key.toCharArray();
if (root == null) root = new TrieNode();
TrieNode cur = root;
cur.val = val;
for (char c : cs) {
if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new TrieNode();
cur = cur.children[c - 'a'];
cur.val += val;
}
return root;
}
int search(TrieNode root, String prefix) {
TrieNode cur = root;
for (char c : prefix.toCharArray()) {
if (cur.children[c - 'a'] != null) cur = cur.children[c - 'a'];
else return 0;
}
return cur.val;
}
Map<String, Integer> mem;
TrieNode root;
public MapSum() {
mem = new HashMap<>();
root = null;
}
public void insert(String key, int val) {
if (!mem.containsKey(key)) {
root = build(root, key, val);
mem.put(key, val);
}
else {
int sub = mem.get(key);
root = build(root, key, val - sub);
mem.put(key, val);
}
}
public int sum(String prefix) {
return search(root, prefix);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年09月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录