Leetcode 133. Clone Graph 一问？

This topic created in 2523 days ago, the information mentioned may be changed or developed.

这段代码什么问题？

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 replies 2019-06-17 14:22:02 +08:00

pwrliang

Jun 17, 2019

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