首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  LeetCode

Leetcode 133. Clone Graph 一问?

  •  
  •   qwertyegg · 173 天前 · 7978 次点击
    这是一个创建于 173 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这段代码什么问题?

    public Node cloneGraph(Node node) {
            if(node == null) return null;
    
            Map<Node, Node> map = new HashMap();
            Queue<Node> queue = new LinkedList();
            List<Node> store = new ArrayList();
            queue.offer(node);
            Node current;
            while(!queue.isEmpty()){
                current = queue.poll();
                map.put(current, new Node(current.val, new ArrayList(current.neighbors.size())));
                store.add(current);
                for(Node neighbor : current.neighbors)
                    if(!map.keySet().contains(neighbor))
                        queue.offer(neighbor);
            }
    
            for(Node n : store)
                for(Node neighbor : n.neighbors)
                    map.get(n).neighbors.add(map.get(neighbor));
            return map.get(node);
        }
    

    input:

    {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
    

    output:

    {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4},{"$ref":"2"},{"$ref":"4"}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
    

    expected output:

    {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
    
    1 回复  |  直到 2019-06-17 14:22:02 +08:00
        1
    pwrliang   172 天前   ♥ 1
    因为你使用 BFS,题目给的例子中:
    1--2
    | |
    4--3

    1 入队,1 出队,然后 2,4 入队;然后 2 出队,1 访问过了跳过,3 入队;然后 4 出队,1 访问过了跳过,3 入队。
    此时,你发现队列存在两个“ 3 ”,造成了重复访问。因此,你在入队前应该检查入队的元素是否访问过。
    把你的代码:
    for(Node neighbor : current.neighbors)
    if(!map.keySet().contains(neighbor))
    queue.offer(neighbor);
    改成:
    for (Node neighbor : current.neighbors)
    if (!map.keySet().contains(neighbor)) {
    // 检查是否访问过,即可 AC
    map.put(neighbor, new Node(neighbor.val, new ArrayList(neighbor.neighbors.size())));
    queue.offer(neighbor);
    }
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2304 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 02:36 · PVG 10:36 · LAX 18:36 · JFK 21:36
    ♥ Do have faith in what you're doing.