讨论/《前缀树》 - 键值映射/
《前缀树》 - 键值映射
共 5 个回复

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

后续的不需要更新吧, 最后算的是前缀的key的和

apple 1
ap 3
ap 8

如果前缀是a/ap, 那么值就需要计算apple和ap
如果前缀是app/appl/apple, 那么就不会计算ap的值只计算apple的值就行

insert 那一步是不是有点问题? 比如 最开始insert (apple,1),insert(ap,3),insert(ap,8);更新的ap,后续的数据ple感觉没有更新呢

C++

class TrieNode{
public:
    TrieNode(char x):c(x){}
private:
    char c;
    int val;
    bool finished=false;
    unordered_map<char,shared_ptr<TrieNode>>child;
    friend class MapSum;
};


class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        root=make_shared<TrieNode>('/');
    }
    
    void insert(string key, int val){
        auto next=root;
        for(int i=0;i<key.size();++i)
        {
            auto c=key[i];
            if(next->child.find(c)!=next->child.end())
                next=next->child[c];
            else
            {
                auto temp=make_shared<TrieNode>(c);
                next->child[c]=temp;
                next=temp;
            }
            if(i==key.size()-1)
            {
                next->finished=true;
                next->val=val;
            }
        }
    }
    
    shared_ptr<TrieNode> getNode(string word){
        auto next=root;
        for(auto c:word)
        {
            if(next->child.find(c)!=next->child.end())
                next=next->child[c];
            else
                return nullptr;
        }
        return next;
    }

    int dfs(shared_ptr<TrieNode> node)
    {
        int ans=0;
        stack<shared_ptr<TrieNode>>stk;
        stk.push(node);
        while(!stk.empty())
        {
            auto node=stk.top();
            stk.pop();
            if(node->finished==true)
                ans+=node->val;
            for(auto [k,v]:node->child)
                stk.push(v);
        }
        return ans;
    }

    int sum(string prefix) {
        auto node=getNode(prefix);
        if(node==nullptr)
            return 0;
        return dfs(node);
    }
private:
    shared_ptr<TrieNode>root;
};

记录每一个前缀树的sum
在Insert方法内,由于要覆盖已存在的键值,若覆盖,则每个节点下的sum还需要减掉旧值

package trie


type MapSum struct {
	sum int
	value int
	isEnd bool
	next map[int32]*MapSum
}


/** Initialize your data structure here. */
func MapSumConstructor() MapSum {
	return MapSum{next: make(map[int32]*MapSum)}
}

func (m *MapSum) Search(key string) (int, bool) {
	node := m
	for _, c := range key {
		if node.next[c] == nil {
			return 0, false
		}
		node = node.next[c]
	}
	if node.isEnd {
		return node.value, true
	}
	return 0, false
}


func (m *MapSum) Insert(key string, val int)  {
	old, _ := m.Search(key)
	val -= old
	node := m
	for _, c := range key {
		if node.next[c] == nil {
			node.next[c] = &MapSum{next: make(map[int32]*MapSum)}
		}
		node = node.next[c]
		node.sum += val
	}
	node.value = val
	node.isEnd = true
}


func (m *MapSum) Sum(prefix string) int {
	node := m
	for _, c := range prefix {
		if node.next[c] == nil {
			return 0
		}
		node = node.next[c]
	}
	return node.sum
}


/**
 * Your MapSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(key,val);
 * param_2 := obj.Sum(prefix);
 */