【LeetCode】键值映射 Java 题解

2021 年 11 月 14 日
本文字数：1295 字
阅读完需：约 4 分钟

题目描述

实现一个 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)
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/map-sum-pairs著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是设计类题目。题目描述定义是实现 map 类，Java 中有很多定义好的 map，我们可以直接使用。
首先，我们使用暴力法解决这个题目，采用 treeMap 存储 k - v, 然后我们遍历每一个 key，看 key 是否包含 prefix。在 Java 中，一般使用 startsWith() 方法检测字符串是否以指定的前缀开始。还有一个常见 contains() 方法用于判断字符串中是否包含指定的字符或字符串。这两个方法，我们在使用的时候要区分清楚，具体实现代码如下：

通过代码

class MapSum {    Map<String, Integer> map;    public MapSum() {        map = new TreeMap<>();    }        public void insert(String key, int val) {        map.put(key, val);    }        public int sum(String prefix) {        int sum = 0;        for (Map.Entry<String, Integer> entry : map.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); */

复制代码

总结

通过代码中使用的 startsWith() 是一个很常见的，写的很好的函数。方便学习，实现代码如下：

    public boolean startsWith(String prefix, int toffset) {        char ta[] = value;        int to = toffset;        char pa[] = prefix.value;        int po = 0;        int pc = prefix.value.length;        // Note: toffset might be near -1>>>1.        if ((toffset < 0) || (toffset > value.length - pc)) {            return false;        }        while (--pc >= 0) {            if (ta[to++] != pa[po++]) {                return false;            }        }        return true;    }