Leetcode 133. Clone Graph 一问？

V2EX = way to explore

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

已注册用户请登录

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

这段代码什么问题？

public Node cloneGraph(Node node) { if(node == null) return null; Map<Node, Node> map = new HashMap(); Queue<Node> queue = new LinkedLst(); 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);
}