LeetCode_前缀树_数据结构设计_中等_677.键值映射

清疚 2023-10-07 20:04 18阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

设计一个 map ，满足以下几点：  
① 字符串表示键，整数表示值  
② 返回具有前缀等于给定字符串的键的值的总和

实现一个 MapSum 类：

MapSum() 初始化 MapSum 对象
    void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 
    key-value 将被替代成新的键值对。
    int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

**示例 1：**  
输入：  
\[“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");           // 返回 3 (apple = 3)
    mapSum.insert("app", 2);    
    mapSum.sum("ap");           // 返回 5 (apple + app = 3 + 2 = 5)

**提示：**  
1 <= key.length, prefix.length <= 50  
key 和 prefix 仅由小写英文字母组成  
1 <= val <= 1000  
最多调用 50 次 insert 和 sum

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/map-sum-pairs

## 2.思路 ##

（1）哈希表  
本题可以使用直接**哈希表**来实现题目的要求，即要将插入的键值对存放到 hashMap 中，而如果要求出以前缀 prefix 开头的键 key 的值的总和，直接**遍历 hashMap 中的键值对**，判断每个键是否包含前缀 prefix，并用变量 sum 进行累加求和即可。

（2）前缀哈希映射  
思路参考[本题官方题解][Link 1]。

（3）前缀树  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————哈希表
    class MapSum {
        
    
        Map<String, Integer> hashMap;
    
        public MapSum() {
        
            hashMap = new HashMap<>();
        }
        
        public void insert(String key, int val) {
        
            hashMap.put(key, val);
        }
        
        public int sum(String prefix) {
        
            int sum = 0;
            for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
        
                if (entry.getKey().startsWith(prefix)) {
        
                    sum += entry.getValue();
                }
            }
            return sum;
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */

//思路2————前缀哈希映射
    class MapSum {
        
    
        Map<String, Integer> hashMap;
        Map<String, Integer> prefixMap;
    
        public MapSum() {
        
            hashMap = new HashMap<>();
            prefixMap = new HashMap<>();
        }
        
        public void insert(String key, int val) {
        
            int diff = val - hashMap.getOrDefault(key, 0);
            hashMap.put(key, val);
            for (int i = 1; i <= key.length(); i++) {
        
                String curPrefix = key.substring(0, i);
                prefixMap.put(curPrefix, prefixMap.getOrDefault(curPrefix, 0) + diff);
            }
        }
        
        public int sum(String prefix) {
        
            return prefixMap.getOrDefault(prefix, 0);
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */

//思路3————前缀树
    class MapSum {
        
    
        class TrieNode {
        
            int val = 0;
            TrieNode[] next = new TrieNode[26];
        }
    
        Map<String, Integer> hashMap;
        TrieNode root;
    
        public MapSum() {
        
            hashMap = new HashMap<>();
            root = new TrieNode();
        }
        
        public void insert(String key, int val) {
        
            int diff = val - hashMap.getOrDefault(key, 0);
            hashMap.put(key, val);
            TrieNode node = root;
            for (char c : key.toCharArray()) {
        
                if (node.next[c - 'a'] == null) {
        
                    node.next[c - 'a'] = new TrieNode();
                }
                node = node.next[c - 'a'];
                node.val += diff;
            }
        }
        
        public int sum(String prefix) {
        
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
        
                if (node.next[c - 'a'] == null) {
        
                    return 0;
                } else {
        
                    node = node.next[c - 'a'];
                }
            }
            return node.val;
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */

[Link 1]: https://leetcode.cn/problems/map-sum-pairs/solution/jian-zhi-ying-she-by-leetcode-solution-j4xy/