leetcode-677-键值映射

键值映射

题面

leetcode题目

实现一个 MapSum 类，支持两个方法，insert 和 sum：

MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

example

输入：

["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)

题解

总体思路

比较朴素的思路是考虑使用字典树(前缀数组)去维护MapSum类，再在进行sum操作时做一次统计。仔细的考虑后可以发现我们实际上可以在维护的途中顺便完成统计，实现对sum操作的优化。当然总体复杂度并没有受到很大的影响。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;
#define _DEBUG

typedef struct Node
{
    struct Node *next[26];
    int val;
    int sum;

    Node()
    {
        for (int i = 0; i < 26; i++)
        {
            next[i] = nullptr;
            this->val = 0;
            this->sum = 0;
        }
    };
} Node;

class MapSum
{
public:
    Node *root;

    MapSum()
    {
        root = new Node();
    }

    void insert(string key, int val)
    {
        Node *now = root;
        for (int i = 0; i < key.length(); i++)
        {
            int keyNum = key[i] - 'a';
            if (now->next[keyNum] == nullptr)
            {
                now->next[keyNum] = new Node();
            }
            now = now->next[keyNum];
        }
        if (now != nullptr)
        {
            if (now->val != val)
            {
                int diff = val - now->val;
                now->val = val;
                Node *newNow = root;
                newNow->sum += diff;
                for (int i = 0; i < key.length(); i++)
                {
                    int keyNum = key[i] - 'a';
                    newNow = newNow->next[keyNum];
                    newNow->sum += diff;
                }
            }
        }
    }

    int sum(string prefix)
    {
        Node *now = root;
        for (int i = 0; i < prefix.length(); i++)
        {
            int keyNum = prefix[i] - 'a';
            if (now->next[keyNum] == nullptr)
            {
                return 0;
            }
            now = now->next[keyNum];
        }

        return now->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);
 */

// for test
int main()
{
    MapSum *obj = new MapSum();
    obj->insert("apple", 3);
    cout << obj->sum("ap") << endl;
    obj->insert("app", 2);
    cout << obj->sum("ap") << endl;
    return 0;
}