leetcode 677. Map Sum Pairs 键值映射

﹏ヽ暗。殇╰゛Y 2022-06-03 08:22 188阅读 0赞

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:  
Input: insert(“apple”, 3), Output: Null  
Input: sum(“ap”), Output: 3  
Input: insert(“app”, 2), Output: Null  
Input: sum(“ap”), Output: 5

本题和上一题一样直接暴力查询即可，本题的本意应该是使用前缀树，但是这个有点麻烦，所以我这里直接暴力去做

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    class MapSum 
    {
    public:
        map<string, int> mmp;
        /** Initialize your data structure here. */
        MapSum() 
        {
    
        }
    
        void insert(string key, int val) 
        {
            mmp[key] = val;
        }
    
        int sum(string prefix) 
        {
            int s = 0;
            for (auto one : mmp)
            {
                if (prefix == one.first.substr(0, prefix.length()))
                    s += one.second;
            }
            return s;
        }
    };
    
    /**
    * Your MapSum object will be instantiated and called as such:
    * MapSum obj = new MapSum();
    * obj.insert(key,val);
    * int param_2 = obj.sum(prefix);
    */