677-键值映射(Map Sum Pairs)

YorkChen 发布于2019-08-19 10:51 / 892人阅读

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

前言

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

实现一个 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 2021-11-16 11:45 评论0 收藏0
LeetCode 677 键值映射[Map] HERODING的LeetCode之路

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

zilu 2021-11-15 11:38 评论0 收藏0
Go语言核心36讲（Go语言实战与应用十三）--学习笔记

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

不知名网友 2021-11-26 11:11 评论0 收藏0
java 键值对按值排序

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

Moxmi 2019-08-16 13:35 评论0 收藏0
493. Reverse Pairs

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

acrazing 2019-08-14 17:36 评论0 收藏0