leetcode
leetcode 551 ~ 600
键值映射

键值映射

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 0.0 MB


/*
 * MapSum class implements a map that supports two operations using Java Streams: 
 * 1. insert(String key, int val): Insert a key-value pair into the map. If the key already exists, update the value.
 * 2. sum(String prefix): Return the sum of all values of keys that start with the given prefix.
 */
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
 
public class MapSum {
    private Map<String, Integer> map;
 
    // Constructor to initialize the map
    public MapSum() {
        map = new HashMap<>();
    }
 
    // Insert a key-value pair into the map
    public void insert(String key, int val) {
        map.put(key, val);
    }
 
    // Return the sum of values for all keys starting with the given prefix using Java Streams
    public int sum(String prefix) {
        return map.entrySet().stream()
                   .filter(entry -> entry.getKey().startsWith(prefix))
                   .collect(Collectors.summingInt(Map.Entry::getValue));
    }
}

解释

方法:

该题解采用了字典和字典树(Trie)的结合方法。主要包括两个部分:1. 一个普通字典 'map' 存储键值对,用于记录每个键对应的最新值。2. 字典树 'root',其中每个节点存储了到该节点为止的所有键的值的累积和。插入操作时,首先计算当前键值与原始值的差值(delta),然后更新字典树中经过该键的所有节点的累积值。查询前缀和时,遍历字典树直到前缀的末尾,然后返回该节点的累积和。

时间复杂度:

O(k) for insert, O(p) for sum

空间复杂度:

O(N*k)

代码细节讲解

🦆
为什么在插入操作中需要计算当前键值与原始值的差值(delta),而不是直接使用新的键值进行更新?
在插入操作中计算当前键值与原始值的差值(delta)是为了正确维护字典树中各节点的累积值。如果直接使用新的键值更新,那么我们将无法区分出键值的增加或减少的部分,导致无法正确调整已存在键的累积和。使用差值(delta)可以确保无论是增加还是减少键值,都能通过加上delta来正确更新所有经过该键的节点的累积和。
🦆
当插入操作中的键已存在于字典中时,原有的节点在字典树中的累积值是如何被正确调整的?
当插入操作中的键已存在于字典中时,首先计算出新值与旧值的差值delta。然后从字典树的根节点开始,遍历到表示该键的每一个字符对应的节点,逐一将delta加到这些节点的累积值中。这样,字典树中经过该键的所有节点的累积值都会被正确地调整,以反映新的键值。
🦆
在查询前缀和的操作中,如果前缀不存在,直接返回0的处理方式是否会影响到其他操作或数据的准确性?
在查询前缀和的操作中,如果前缀不存在,直接返回0是一个合理的处理方式,因为这意味着没有任何键是以该前缀开始的,因此前缀和自然应该是0。这种处理方式不会影响其他操作或数据的准确性,因为它仅仅反映了前缀和查询的结果,并不改变任何存储或累积值。
🦆
字典树的根节点在每次插入操作时都更新其累积值,这种设计有什么特别的优点或原因?
字典树的根节点在每次插入操作时都更新其累积值,这样设计的主要优点是方便快速地获取所有键的总累积和。根节点的累积值代表了所有存储在字典树中的键的值的总和,这使得任何时候对整体键值的累积查询变得非常高效。此外,更新根节点的累积值也是维护整个字典树数据一致性的关键步骤。

相关问题