|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 实现一个 MapSum 类,支持两个方法,insert 和 sum:
- MapSum() 初始化 MapSum 对象
- void insert(String key, int val) 插入 key-val 键值对,字符串表示键 key ,整数表示值 val 。如果键 key 已经存在,那么原来的键值对将被替代成新的键值对。
- int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
-  
- 示例:
- 输入:
- inputs = ["MapSum", "insert", "sum", "insert", "sum"]
- inputs = [[], ["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)
-  
- 提示:
- 1 <= key.length, prefix.length <= 50
- key 和 prefix 仅由小写英文字母组成
- 1 <= val <= 1000
- 最多调用 50 次 insert 和 sum
-  
- 注意:本题与主站 677 题相同: https://leetcode-cn.com/problems/map-sum-pairs/
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/z1R5dt
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class MapSum {
- private:
- struct Trie{
- set<string>words;
- map<char, Trie*>next;
- };
- Trie* root;
- map<string, int>score;
- public:
- /** Initialize your data structure here. */
- MapSum() {
- root = new Trie();
- }
-
- void insert(string key, int val) {
- score[key] = val;
- //构建前缀树
- int len = key.size();
- Trie* node = root;
- for(int i = 0; i < len; i++){
- if((node -> next).count(key[i]) == 0){
- node -> next[key[i]] = new Trie();
- }
- node = node -> next[key[i]];
- (node -> words).insert(key);
- }
- }
-
- int sum(string prefix) {
- //查找前缀
- int res = 0;
- Trie* node = root;
- for(auto cha : prefix){
- if((node -> next).count(cha) == 0){
- return 0;
- }
- node = node -> next[cha];
- }
- for(auto it = (node -> words).begin(); it != (node -> words).end(); it++){
- res += score[*it];
- }
- 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);
- */
复制代码 |
|