脚本宝典收集整理的这篇文章主要介绍了

677-键值映射(Map Sum Pairs)

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

前言

前缀树同系列的题目,可以用前缀树的思路来存储,只需要基于之前的前缀树实现改造。原题目要求如下:

实现一个 MapSum 类里的两个方法,insert 和 sum。

对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。

对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

实现思路

  1. 参考前缀树实现的思路,把节点中的boolean变量改为键值对的值
  2. sum方法的时候首先要找到匹配前缀的节点,然后用层序遍历(广度优先)方式去遍历这个节点的子树。遍历的时候使用递归进行遍历。

实例代码

public class MapSum {
    /**
     * key的前缀字符
     */
    char keyPrefix;
    /**
     * 子节点
     */
    MapSum[] children;
    /**
     * 存储的值,不为0则为终止节点
     */
    int value;

    /** Initialize your data structure here. */
    public MapSum() {
        children=new MapSum[26];
        value=0;
    }

    /**
     * 字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。
     * @param key 键
     * @param val 值
     */
    public void insert(String key, int val) {
        if(key!=null){
            //分解成字符数组
            char[] charArr=key.toCharArray();
            //模拟指针操作,记录当前访问到的树的节点
            MapSum currentNode=this;
            for(int i=0;i<charArr.length;i++){
                char currentChar=charArr[i];
                //根据字符获取对应的子节点
                MapSum node=currentNode.children[currentChar-97];
                if(node!=null && node.keyPrefix==currentChar){//判断节点是否存在
                    currentNode=node;
                }else{//不存在则创建一个新的叶子节点,并指向当前的叶子节点
                    node=new MapSum();
                    node.keyPrefix=currentChar;
                    currentNode.children[currentChar-97]=node;
                    currentNode=node;
                }
            }
            //存储值
            currentNode.value=val;
        }else{
            this.value=val;
        }
    }

    /**
     * 根据表示前缀的字符串,返回所有以该前缀开头的键的值的总和。
     * @param prefix 前缀
     * @return
     */
    public int sum(String prefix) {
        int result=0;
        //前缀是否匹配
        boolean match=true;
        if(prefix!=null && !prefix.trim().equals("")){
            char[] prefixChar=prefix.toCharArray();
            MapSum currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                MapSum node=currentNode.children[currentChar-97];
                if(node!=null && node.keyPrefix==currentChar){//判断节点是否存在
                    currentNode=node;
                }else{
                    match=false;
                    break;
                }
            }
            if(match){//前缀匹配后开始检索这个匹配节点后续的子树
                result=sumByFloor(currentNode);
            }
        }
        return result;
    }

    /**
     * 层序遍历(广度优先)方式访问树
     * @param mapSum
     * @return
     */
    private int sumByFloor(MapSum mapSum){
        int result=0;
        if(mapSum==null){
            return 0;
        }else{
            result+=mapSum.value;
            MapSum[] mapSums=mapSum.children;
            for(MapSum sum:mapSums){
                if(sum!=null){
                    result+=sumByFloor(sum);
                }else{
                    result+=sumByFloor(sum);
                }
            }
        }
        return result;
    }
}

总结

以上是脚本宝典为你收集整理的

677-键值映射(Map Sum Pairs)

全部内容,希望文章能够帮你解决

677-键值映射(Map Sum Pairs)

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过