C++刷leetcode（677. 键值映射）【字典树】
题目描述:实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/map-sum-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class MapSum {
private:
bool isEnd;
MapSum* next;
vector<int> value;
set<string> store;
public:
/** Initialize your data structure here. */
MapSum() {
isEnd = false;
memset(next, 0, sizeof(next));
value = {};
}
void insert(string key, int val) {
MapSum* node = this;
auto cha = store.insert(key);
bool flag = cha.second;
for(auto cha : key){
if(node -> next == NULL){
node -> next = new MapSum();
}
node = node -> next;
if(flag == false)node -> value.pop_back();
node ->value.push_back(val);
}
node -> isEnd = true;
}
int sum(string prefix) {
MapSum*node = this;
int res = 0;
for(auto cha : prefix){
if(node -> next == NULL) return res;
node = node -> next;
}
int len = node -> value.size();
for(int i = 0; i < len; i++){
res += node -> value;
}
return res;
}
};
/**
* 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]