Leetcode 133. Clone Graph 一问？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2020 天前的主题，其中的信息可能已经有所发展或是发生改变。

这段代码什么问题？

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

pwrliang

2019-06-17 14:22:02 +08:00

因为你使用 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);
}