讨论/《前缀树》 - 键值映射/
《前缀树》 - 键值映射

0ms 100% 插入时维护路径上的和, 如果该元素是重复元素, 则考虑差值更新

class MapSum {
public:
    MapSum *root[26];
    int val;
    // 如果是-1 表示不是终止节点
    // 如果不为-1 则值为该变量实际的值
    int isEnd;
    /** Initialize your data structure here. */
    MapSum() {
        for(int i=0;i<26;i++)
            root[i] = nullptr;
        val = 0;
        isEnd = -1;
    }

    int find(string s){
        MapSum *now = this;
        for(auto ch : s){
            if(now->root[ch - 'a'] == nullptr)
                return -1;
            now = now->root[ch - 'a'];
        }
        return now->isEnd;
    }

    void insert(string key, int val) {
        int preval = find(key);
        int trueval = val;
        if(preval != -1)
            val = val - preval;
        MapSum *now = this;
        for(auto ch : key){
            if(now->root[ch - 'a'] == nullptr)
                now->root[ch - 'a'] = new MapSum();
            now->val += val;
            now = now->root[ch - 'a'];
        }
        now->val += val;
        now->isEnd = trueval;
    }
    
    int sum(string prefix) {
        MapSum *now = this;
        for(auto ch : prefix){
            if(now->root[ch - 'a'] == nullptr){
                return 0;
            }
            now = now->root[ch - 'a'];
        }
        return now->val;
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */
1
展开全部 6 讨论