677-鍵值映射(Map Sum Pairs)

YorkChen 發(fā)布于2019-08-19 10:51 / 1002人閱讀

摘要：前言前綴樹(shù)同系列的題目，可以用前綴樹(shù)的思路來(lái)存儲(chǔ)，只需要基于之前的前綴樹(shù)實(shí)現(xiàn)改造。對(duì)于方法，你將得到一對(duì)字符串，整數(shù)的鍵值對(duì)。字符串表示鍵，整數(shù)表示值。實(shí)例代碼的前綴字符子節(jié)點(diǎn)存儲(chǔ)的值，不為則為終止節(jié)點(diǎn)字符串表示鍵，整數(shù)表示值。

前言

前綴樹(shù)同系列的題目，可以用前綴樹(shù)的思路來(lái)存儲(chǔ)，只需要基于之前的前綴樹(shù)實(shí)現(xiàn)改造。原題目要求如下：

實(shí)現(xiàn)一個(gè) MapSum 類里的兩個(gè)方法，insert 和 sum。對(duì)于方法 insert，你將得到一對(duì)（字符串，整數(shù)）的鍵值對(duì)。字符串表示鍵，整數(shù)表示值。如果鍵已經(jīng)存在，那么原來(lái)的鍵值對(duì)將被替代成新的鍵值對(duì)。
對(duì)于方法 sum，你將得到一個(gè)表示前綴的字符串，你需要返回所有以該前綴開(kāi)頭的鍵的值的總和。
示例 1:
輸入: insert("apple", 3), 輸出: Null
輸入: sum("ap"), 輸出: 3
輸入: insert("app", 2), 輸出: Null
輸入: sum("ap"), 輸出: 5

實(shí)現(xiàn)思路

參考前綴樹(shù)實(shí)現(xiàn)的思路，把節(jié)點(diǎn)中的boolean變量改為鍵值對(duì)的值

sum方法的時(shí)候首先要找到匹配前綴的節(jié)點(diǎn)，然后用層序遍歷(廣度優(yōu)先)方式去遍歷這個(gè)節(jié)點(diǎn)的子樹(shù)。遍歷的時(shí)候使用遞歸進(jìn)行遍歷。

實(shí)例代碼

public class MapSum {
    /**
     * key的前綴字符
     */
    char keyPrefix;
    /**
     * 子節(jié)點(diǎn)
     */
    MapSum[] children;
    /**
     * 存儲(chǔ)的值，不為0則為終止節(jié)點(diǎn)
     */
    int value;

    /** Initialize your data structure here. */
    public MapSum() {
        children=new MapSum[26];
        value=0;
    }

    /**
     * 字符串表示鍵，整數(shù)表示值。如果鍵已經(jīng)存在，那么原來(lái)的鍵值對(duì)將被替代成新的鍵值對(duì)。
     * @param key 鍵
     * @param val 值
     */
    public void insert(String key, int val) {
        if(key!=null){
            //分解成字符數(shù)組
            char[] charArr=key.toCharArray();
            //模擬指針操作,記錄當(dāng)前訪問(wèn)到的樹(shù)的節(jié)點(diǎn)
            MapSum currentNode=this;
            for(int i=0;i