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

Leetcode 133. Clone Graph 一问?

  •  
  •   qwertyegg · 2019-06-17 02:38:26 +08:00 · 13711 次点击
    这是一个创建于 1747 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这段代码什么问题?

    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
        1
    pwrliang  
       2019-06-17 14:22:02 +08:00   ❤️ 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);
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5759 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 06:12 · PVG 14:12 · LAX 23:12 · JFK 02:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.