【Day 74 】2023-01-13 - 677. 键值映射

[azl397985856]

677. 键值映射

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/map-sum-pairs

前置知识

• 哈希表
• Trie
• DFS

  题目描述

  实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null 输入: sum("ap"), 输出: 3 输入: insert("app", 2), 输出: Null 输入: sum("ap"), 输出: 5

[whoam-challenge]

class MapSum: def init(self): self.map = {}

def insert(self, key: str, val: int) -> None:
    self.map[key] = val

def sum(self, prefix: str) -> int:
    res = 0
    for key,val in self.map.items():
        if key.startswith(prefix):
            res += val
    return res

[snmyj]

class MapSum {
public:
    map<string,int> mapsum;
    MapSum() {

    }

    void insert(string key, int val) {
        mapsum[key]=val;
    }

    int sum(string prefix) {
        int sum=0;
     for(auto [x,val]:mapsum){
         if(x.substr(0,prefix.length())==prefix){
            sum+=val;
         }
     }    
        return sum; 
     }   

};

[Elon-Lau]

class MapSum { public: map<string,int> mapsum; MapSum() {

}

void insert(string key, int val) {
    mapsum[key]=val;
}

int sum(string prefix) {
    int sum=0;
 for(auto [x,val]:mapsum){
     if(x.substr(0,prefix.length())==prefix){
        sum+=val;
     }
 }    
    return sum; 
 }   

};

[JancerWu]

// 字典树
class MapSum {

    class Node{
        Node[] childs;
        int val = 0;
        Node() {
            childs = new Node[26];
        }
    }

    Node root;

    public MapSum() {
        root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = root;
        for (char c : key.toCharArray()) {
            if (cur.childs[c-'a'] == null) {
                cur.childs[c-'a'] = new Node();
            }
            cur = cur.childs[c-'a'];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.childs[c-'a'] == null) {
                return 0;
            }
            cur = cur.childs[c-'a'];
        }
        return dfs(cur);
    }

    public int dfs(Node cur) {
        if (cur == null) return 0;
        int ans = 0;
        ans += cur.val;
        for (Node next : cur.childs) {
            ans += dfs(next);
        }
        return ans;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

[Elsa-zhang]

class TrieNode:
    def __init__(self):
        self.count = 0 # 表示以该处节点构成的串的个数
        self.preCount = {} # 表示以该处节点构成的前缀的字串的个数
        self.children = {}

class MapSum:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int):
        node = self.root
        for w in key:
            if w not in node.children:
                node.children[w]=TrieNode()
            node = node.children[w]
            node.preCount[key] = val

    def sum(self, prefix: str):
        node = self.root
        for w in prefix:
            if w not in node.children:
                return 0
            node = node.children[w]
        return sum([v for v in node.preCount.values()])

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

[bookyue]

code

class MapSum {
    private final MapSum[] children;
    private final Map<String, Integer> map;
    private int val;

    public MapSum() {
        children = new MapSum[26];
        map = new HashMap<>();
        val = 0;
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        MapSum node = this;
        for (char c : key.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null)
                node.children[idx] = new MapSum();

            node = node.children[idx];
            node.val += delta;
        }
    }

    public int sum(String prefix) {
        MapSum node = this;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null) return 0;

            node = node.children[idx];
        }

        return node.val;
    }
}

[mayloveless]

思路

哈希记录key-val，再记录一个前缀的key-val，val为sum，每插入一个字符串，把所有可能前缀都找出来一起更新最新值。

代码

var MapSum = function() {
    this.map = new Map();
    this.prefixmap = new Map();
};

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function(key, val) {
    const oldVal = this.map.get(key) ?? 0;
    this.map.set(key, val);
    for (let i = 1; i <= key.length; ++i) {
        const currprefix = key.substring(0, i);
        const updateVal = (this.prefixmap.get(currprefix) ?? 0) - oldVal + val;
        this.prefixmap.set(currprefix, updateVal);
    }
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function(prefix) {
    return this.prefixmap.get(prefix) ?? 0;
};

复杂度

时间：O(n2) 空间：O)(kn)

[Abby-xu]

class MapSum:

def __init__(self):
    self.dic = {}

def insert(self, key: str, val: int) -> None:
    self.dic[key] = val

def sum(self, prefix: str) -> int:
    out, n = 0, len(prefix)
    for item in self.dic:
        if item[:n] == prefix:
            out += self.dic[item]
    return out

[Jetery]

class MapSum {
public:
    static const int N = 3010;
    int son[N][26];
    int idx;
    int cnt[N];
    unordered_map<string, int> M;
    MapSum() {
        idx = 0;
        memset(cnt, 0, sizeof cnt);
        memset(son, 0, sizeof son);
    }

    void insert(string key, int val) {
        int p = 0;
        for(int i = 0; i < key.size(); i++){
            int u = key[i] - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
            if (M.count(key)) cnt[p] += (val - M[key]);
            else cnt[p] += val;            
        }
        M[key] = val;
    }

    int sum(string prefix) {
        int p = 0;
        for(int i = 0; i < prefix.size(); i++){
            int u = prefix[i] - 'a';
            if (!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */

[A-pricity]

const treeNode = function() {
    this.childNode = new Array(26).fill(0);
    this.isEnd = false;
    this.val = null;
}

var MapSum = function() {
    this.tree = new treeNode()
};

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function(key, val) {
    let curr = this.tree;
    for(const x of key){
        const idx = x.charCodeAt() - 'a'.charCodeAt()
        if(curr.childNode[idx] === 0){
            curr.childNode[idx] = new treeNode();
        }
        curr = curr.childNode[idx]

    }
    curr.isEnd = true;
    curr.val = val;
    // console.log(this.tree)
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function(prefix) {
    let curr = this.tree;
    for(const x of prefix){
        const idx = x.charCodeAt() - 'a'.charCodeAt();
        if(curr.childNode[idx] === 0){return null}
        curr = curr.childNode[idx];
    }
    if(curr === 0){return null}

    function dfs(root){
        const children = root.childNode;
        let sum = 0;
        if(root.isEnd){sum += root.val}
        for(const x of children){
            if(x !== 0){
                sum += dfs(x)
            }
        }

        return sum;
    }
    return dfs(curr)
};```

[klspta]

class MapSum {

    private Node node;

    private Map<String, Integer> map;

    public MapSum() {
        node = new Node();
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        Node cur = node;
        int last = map.getOrDefault(key, 0);
        map.put(key, val);
        val = val - last;
        for(int i = 0; i < key.length(); i++){
            int c = key.charAt(i) - 'a';
            Node next = cur.nexts[c];
            if(next == null){
                cur.nexts[c] = new Node();
            }
            next = cur.nexts[c];
            next.val = next.val + val;
            cur.nexts[c] = next;
            cur = next;
        }
    }

    public int sum(String prefix) {
        Node cur = node;
        for(int i = 0; i < prefix.length(); i++){
            cur = cur.nexts[prefix.charAt(i) - 'a'];
            if(cur == null){
                return 0;
            }
        }
        return cur.val;
    }
}

class Node{
    Node[] nexts;
    int val;
    boolean end;
    public Node(){
        nexts = new Node[26];
        val = 0;
        end = false;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

[paopaohua]

class MapSum {
    Map<String, Integer> map;

    public MapSum() {
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        int res = 0;
        for (String s : map.keySet()) {
            if (s.startsWith(prefix)) {
                res += map.get(s);
            }
        }
        return res;
    }
}

[tiandao043]

class MapSum {
private:
    bool isEnd;
    MapSum* next[26];
    int value;

    int dfs(MapSum* root){
        if(!root) return 0;
        int res=0;
        if(root->isEnd)res+=root->value;
        for(MapSum* cur : root->next){
            res+=dfs(cur);
        }
        return res;
    }

public:
    /** Initialize your data structure here. */
    MapSum() {
        isEnd=false;
        memset(next,0,sizeof(next));
        value=0;
    }

    void insert(string key, int val) {
        MapSum* m=this;
        for(char ch : key){
            if(m->next[ch-'a']==NULL){
                m->next[ch-'a']=new MapSum();
            }
            m=m->next[ch-'a'];
        }
        m->isEnd=true;
        m->value=val;
    }

    int sum(string prefix) {
        MapSum* m=this;
        for(char ch : prefix){
            if(m->next[ch-'a']==NULL){
                return 0;           
            }
            m=m->next[ch-'a'];
        }
        return dfs(m);
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */

[Ryanbaiyansong]

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.val = 0
class MapSum:

    def __init__(self):
        self.root = TrieNode()
        self.d = {}

    def insert(self, key: str, val: int) -> None:
        delta = val
        if key in self.d:
            prev_val = self.d[key]
            delta = val - prev_val
        self.d[key] = val
        cur = self.root 
        for ch in key:
            cur = cur.children[ch]
            cur.val += delta

    def sum(self, prefix: str) -> int:
        cur = self.root
        res = 0
        for ch in prefix:
            if cur is None or ch not in cur.children:
                return 0
            cur = cur.children[ch]
        return cur.val

# a 3
# ap 3
# b 2 
# a 3

# apple 3
# ap   3
# app 2
# apple 2
# ap  7

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

[buer1121]

class MapSum: def init(self): self.map = {} self.prefixmap = {}

def insert(self, key: str, val: int) -> None:
    delta = val
    if key in self.map:
        delta -= self.map[key]
    self.map[key] = val
    for i in range(len(key)):
        currprefix = key[0:i+1]
        if currprefix in self.prefixmap:
            self.prefixmap[currprefix] += delta
        else:
            self.prefixmap[currprefix] = delta

def sum(self, prefix: str) -> int:
    if prefix in self.prefixmap:
        return self.prefixmap[prefix]
    else:
        return 0

[RestlessBreeze]

code

class MapSum {
public:
    MapSum() {

    }

    void insert(string key, int val) {
        cnt[key] = val;
    }

    int sum(string prefix) {
        int res = 0;
        for (auto & [key,val] : cnt) {
            if (key.substr(0, prefix.size()) == prefix) {
                res += val;
            }
        }
        return res;
    }
private:
    unordered_map<string, int> cnt;
};