老师,关于leetcode的677问题

来源:10-6 Trie字典树和字符串映射

天上掉下个小馅饼

2018-12-13

老师,我自己试了一下是成功的,但是在leetcode是失败,我想问一下是我的代码有哪里错了吗

import java.util.TreeMap;

public class Test {
    public static void main(String[] args) {
        MapSum sum = new MapSum();
        sum.insert("apple", 5);
        sum.insert("app", 3);
        System.out.println(sum.sum("a"));
    }
}


class MapSum {

    private class Node {
        public boolean isWord;
        public int value;
        public TreeMap<Character, Node> next;

        public Node(boolean isWord, int value) {
            this.isWord = isWord;
            this.value = value;
            next = new TreeMap<>();
        }

        public Node(boolean isWord) {
            this(isWord, 0);
        }

        public Node() {
            this(false, 0);
        }

        public Node set(int value) {
            this.value = value;
            return this;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public MapSum() {
        root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = root;
        for(int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node(false, val));
            else
                cur.next.put(c, cur.next.get(c).set(cur.next.get(c).value + val));
            cur = cur.next.get(c);
        }
        if(!cur.isWord) {
            cur.isWord = true;
        }
    }

    public int sum(String prefix) {
        Node cur = root;
        for(int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null)
                return 0;
            cur = cur.next.get(c);
        }
        return cur.value;
    }

}

写回答

2回答

liuyubobobo

2018-12-13

我尝试提交你的代码,结果是Wrong Answer。Leetcode给出Wrong Answer后,会给出应用你的代码产生错误的测试用例,如下图所示:

//img.mukewang.com/szimg/5c1154e600014e8107050190.jpg


这个input的意思就是(上一行是调用,下一行是参数):

MapSum mapSum = new MapSum();
mapSum.insert("aa",3);
System.out.println(mapSum.sum("a")); // 应该输出3,你的结果是对的
mapSum.insert("aa",2);
System.out.println(mapSum.sum("a")); // 应该输出2,你的结果输出了5是错的


根据这个测试用例,再调试一下,看看自己的代码哪里有问题?:)


课程的官方github提供了课程的源码。如果有必要,可以参考。关于这一小节的源码,传送门:https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/10-Trie/06-Trie-and-Map/src/MapSum.java


加油!:)


===========


我在本地测试你的代码结果是错误的:

//img.mukewang.com/szimg/5c11d8c80001e33821120690.jpg

0
3
天上掉下个小馅饼
回复
liuyubobobo
老师,麻烦您看一下我上传的截图,就在回答里,麻烦啦:>
2018-12-13
共3条回复

天上掉下个小馅饼

提问者

2018-12-13

老师,麻烦您看一下我这个截图

//img.mukewang.com/szimg/5c11e1ae00012dfb19311031.jpg

//img.mukewang.com/szimg/5c11e1ae0001470018941028.jpg


0
3
天上掉下个小馅饼
回复
liuyubobobo
老师,我知道自己哪里错了,我并没有实现相同字符串的话就替换键值的操作,非常感谢老师,老师回复真的快!!!:>
2018-12-13
共3条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程