百度上怎么做网站,品牌传播策略,网站制作的步骤,网站备案被注销 接入商1. 题目
实现一个 MapSum 类里的两个方法#xff0c;insert 和 sum。
对于方法 insert#xff0c;你将得到一对#xff08;字符串#xff0c;整数#xff09;的键值对。字符串表示键#xff0c;整数表示值。如果键已经存在#xff0c;那么原来的键值对将被替代成新的键…1. 题目
实现一个 MapSum 类里的两个方法insert 和 sum。
对于方法 insert你将得到一对字符串整数的键值对。字符串表示键整数表示值。如果键已经存在那么原来的键值对将被替代成新的键值对。
对于方法 sum你将得到一个表示前缀的字符串你需要返回所有以该前缀开头的键的值的总和。
输入: insert(apple, 3), 输出: Null
输入: sum(ap), 输出: 3
输入: insert(app, 2), 输出: Null
输入: sum(ap), 输出: 52. Trie树解题
参考Trie树
class TrieNode
{
public:TrieNode *next[26];int count;TrieNode():count(0){memset(next,NULL,26*sizeof(TrieNode*));}~TrieNode(){}
};class MapSum {TrieNode *root;
public:/** Initialize your data structure here. */MapSum() {root new TrieNode();}void insert(string key, int val) {TrieNode *cur root;for(char ch:key){if(cur-next[ch-a] NULL)cur-next[ch-a] new TrieNode();cur cur-next[ch-a];}cur-count val;}int sum(string prefix) {TrieNode *cur root;for(char ch:prefix){if(cur-next[ch-a] NULL)return 0;elsecur cur-next[ch-a];}int sumVal 0;sumVal cur-count;for(int i 0; i 26; i)if(cur-next[i])sumVal sum(cur-next[i]);return sumVal;}
private:int sum(TrieNode *root)//递归求和{int subsum 0;if(root NULL)return 0;subsum root-count;for(int i 0; i 26; i)if(root-next[i])subsum sum(root-next[i]);return subsum;}
};class trie{ // 2021.8.28
public:int v 0;trie* next[26] {NULL};void insert(string s, int val){trie* cur this;for(auto ch : s){if(!cur-next[ch-a])cur-next[ch-a] new trie();cur cur-next[ch-a];}cur-v val;}void find(trie* root, string s, int i, int sum){if(!root) return;if(is.size()root-next[s[i]-a])find(root-next[s[i]-a], s, i1, sum);else if(is.size()){sum root-v;for(int j 0; j 26; j){if(root-next[j]){find(root-next[j], s, i, sum);}}}}
};
class MapSum {trie* root;
public:/** Initialize your data structure here. */MapSum() {root new trie();}void insert(string key, int val) {root-insert(key,val);}int sum(string prefix) {int tot 0;root-find(root, prefix, 0, tot);return tot;}
};/*** Your MapSum object will be instantiated and called as such:* MapSum* obj new MapSum();* obj-insert(key,val);* int param_2 obj-sum(prefix);*/
