[数据结构与算法]LeetCode-每日一题677. 键值映射 [Java实现]

实现一个 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 值，我们可以将其拆分为 char 数组并对其进行树化，在叶子节点储存对应的 val 并进行实时更新，在查找时从根节点向下查找，若查找到最后一个非空节点仍未找完则返回 0.

class MapSum {

        private static final TreeNode ROOT = new TreeNode();
        // 利用 Map 记录，防止相同 key 录入使得结果累加，在检查 key 时调用
        private static final HashMap<String, Integer> MAP = new HashMap<>();

        public void insert(String key, int val) {
            int init = val - MAP.getOrDefault(key, 0);
            MAP.put(key, val);
            TreeNode node = ROOT;
            for (char c : key.toCharArray()) {
                if (node.next[c-'a'] == null) {
                    node.next[c-'a'] = new TreeNode();
                }
                node = node.next[c-'a'];
                node.value += init;
            }
        }

        public int sum(String prefix) {
            TreeNode node = ROOT;
            for (char c : prefix.toCharArray()) {
                if (node.next[c-'a'] == null) return 0;
                node = node.next[c-'a'];
            }
            return node.value;
        }

        private static class TreeNode {
            private int value = 0;
            private final TreeNode[] next = new TreeNode[26];
        }
    }