资讯专栏INFORMATION COLUMN

677-键值映射(Map Sum Pairs)

YorkChen / 1000人阅读

摘要:前言前缀树同系列的题目,可以用前缀树的思路来存储,只需要基于之前的前缀树实现改造。对于方法,你将得到一对字符串,整数的键值对。字符串表示键,整数表示值。实例代码的前缀字符子节点存储的值,不为则为终止节点字符串表示键,整数表示值。

前言

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

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

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

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

示例 1:

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

实现思路

参考前缀树实现的思路,把节点中的boolean变量改为键值对的值

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           
               
                                           
                       
                 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76582.html

相关文章

  • 【快乐水题】677. 键值映射

    摘要:原题力扣链接键值映射题目简述实现一个类,支持两个方法,和初始化对象插入键值对,字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。返回所有以该前缀开头的键的值的总和。 ...

    sean 评论0 收藏0
  • LeetCode 677 键值映射[Map] HERODING的LeetCode之路

    摘要:解题思路这道题可以开挂一波,反向套娃,你让我实现键值映射,那我就用键值映射实现,直接定义一个,用来记录和对,函数实现时,通过来统计拥有的值的和,代码如下 解题思路...

    zilu 评论0 收藏0
  • Go语言核心36讲(Go语言实战与应用十三)--学习笔记

    摘要:在第二种方案中,我们封装的结构体类型的所有方法,都可以与类型的方法完全一致包括方法名称和方法签名。所以在设计这样的结构体类型的时候,只包含类型的字段就不够了。当参数或的实际类型不符合要求时,方法会立即引发。35 | 并发安全字典sync.Map (下)我们在上一篇文章中谈到了,由于并发安全字典提供的方法涉及的键和值的类型都是interface{},所以我们在调用这些方法的时候,往往还需要对键...

    不知名网友 评论0 收藏0
  • java 键值对 按值排序

    摘要:在最近写程序题的时候,需要存储一个为为的后来需要根据的长度对从小到大进行排序。用代替,然后中的元素为配对类,变相实现了一个键对应一个值的集合,并且能够排序。 在最近写程序题的时候,需要存储一个key为char,value为string的map,后来需要根据string的长度对map从小到大进行排序。 showImg(https://segmentfault.com/img/bVbiZz...

    Moxmi 评论0 收藏0
  • 493. Reverse Pairs

    摘要:题目链接和还有是一类题,解法都差不多。可以做,但是这道题如果输入是有序的,简单的会超时,所以得用来做。算的方法是比如给的例子,现在分成了左右两部分,拿两个指针和。 493. Reverse Pairs 题目链接:https://leetcode.com/problems... 和Count of Smaller Numbers After Self还有count of range su...

    acrazing 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<