专栏首页Leetcode名企之路【Leetcode】133.克隆图

【Leetcode】133.克隆图

题目

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 valInt) 和其邻居的列表(list[Node])。

示例:

img

输入:
{"$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 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

提示:

  1. 节点数介于 1 到 100 之间。
  2. 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  3. 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  4. 必须将给定节点的拷贝作为对克隆图的引用返回。

题解

这道题目是图的遍历,节点遍历我们很熟悉,要么dfs,要么dfs。关键点是:图的边怎么复制。为了复制两个节点之间边的关系,我们用一个map去记录原节点和新节点之间的对应关系,这样遍历节点的的时候我们就可以通过map 查到复制节点的,把他们的边复制上。我们先采用bfs的方式来复制图。

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        Node copyNode = new Node();
        copyNode.val = node.val;
        map.put(node, copyNode);

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.neighbors == null) {
                continue;
            }

            if (map.get(current).neighbors == null) {
                map.get(current).neighbors = new LinkedList<>();
            }

            List<Node> neighbors = current.neighbors;
            List<Node> copiedNeighbors = new LinkedList<>();
            for (Node neighbor : neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.add(neighbor);
                    Node tmp = new Node();
                    tmp.val = neighbor.val;
                    map.put(neighbor, tmp);
                }
                map.get(current).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}

采用dfs的递归方式来复制图。

class Solution {
    public Node cloneGraph(Node node) {
        Map<Node, Node> resNode2CopyNode = new HashMap<>();
        return helper(node, resNode2CopyNode);
    }

    public Node helper(Node node, Map<Node, Node> resNode2CopyNode) {
        if (node == null) return null;
        if (!resNode2CopyNode.containsKey(node)) {
            Node tmp = new Node();
            tmp.val = node.val;
            resNode2CopyNode.put(node, tmp);
        }
        Node copy = resNode2CopyNode.get(node);
        if (node.neighbors == null) {
            return copy;
        }

        copy.neighbors = new LinkedList<>();
        List<Node> neighbors = node.neighbors;
        for (Node neighbor : neighbors) {
            Node copyNeighbor = null;
            if (resNode2CopyNode.containsKey(neighbor)) {
                copyNeighbor = resNode2CopyNode.get(neighbor);
            } else {
                copyNeighbor = helper(neighbor, resNode2CopyNode);
            }

            copy.neighbors.add(copyNeighbor);
        }    
        return copy;
    }
}

采用dfs迭代的方式来解。

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> resNode2CopyNode = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        Node copy = new Node();
        copy.val = node.val;
        resNode2CopyNode.put(node, copy);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            List<Node> neighbors = current.neighbors;
            if (neighbors == null) {
                continue;
            }

            Node copyNode = resNode2CopyNode.get(current);
            if (copyNode.neighbors == null) {
                copyNode.neighbors = new LinkedList<>();
            }

            for (Node neighbor : neighbors) {
                Node copyNeighbor = null;
                if (resNode2CopyNode.containsKey(neighbor)) {
                    copyNeighbor = resNode2CopyNode.get(neighbor);
                } else {
                    copyNeighbor = new Node();
                    copyNeighbor.val = neighbor.val;
                    resNode2CopyNode.put(neighbor, copyNeighbor);
                    stack.push(neighbor);
                }
                copyNode.neighbors.add(copyNeighbor);
            }
        }
        return copy;
    }
}

本文分享自微信公众号 - Leetcode名企之路(DailyLeetCode),作者:码蹄疾

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 百度社招面试题——如何用Redis实现分布式锁

    关于Redis实现分布式锁的问题,网络上很多,但是很多人的讨论基本就是把原来博主的贴过来,甚至很多面试官也是一知半解经不起推敲就来面候选人,最近结合我自己的学习...

    Leetcode名企之路
  • 【Leetcode】129.求根到叶子节点数字之和

    给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

    Leetcode名企之路
  • 【Leetcode】124. 二叉树中的最大路径和

    本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    Leetcode名企之路
  • LeetCode 133. 克隆图(图的BFS/DFS)

    给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。

    Michael阿明
  • 剑指Offer面试题:16.合并两个排序的链表

    PS:这也是一道出镜率极高的面试题,我相信很多童鞋都会很眼熟,就像于千万人之中遇见不期而遇的人,没有别的话可说,唯有轻轻地问一声:“哦,原来你也在这里? ”

    Edison Zhou
  • 第一章:NodeJS 概述

    Node 概述 什么是 Node Node.js® is a JavaScript runtime built on Chrome's V8 JavaScrip...

    老马
  • 【专业技术】Node.js 究竟是什么?

    简介 如果您听说过 Node,或者阅读过一些文章,宣称 Node 是多么多么的棒,那么您可能会想:“Node 究竟是什么东西?” 即便是在参阅 Node 的主页...

    程序员互动联盟
  • 深入浅出 Nodejs ( 一 ) :Nodejs 的简介

    我认为 Node 是一门独具风格的技术,它的特点很有意思,本章我们主要讲 Node 的特点,Node 应用场景以及 Node 的使用者。

    serena
  • 按深度打印二叉树节点数据

    之前去面试,被问到了一个关于二叉树的问题,本身对算法并不擅长,结果想了半天没想出解决方法,经过面试官提点,才恍然大悟,回来后立马把实现写了出来,详见如下...

    RedSheep
  • 图解 K8S 控制器 Node 生命周期管理

    Node其实就对应着kubernetes中的工作组件,今天我们来看下kubernetes中针对Node的生命周期的管理包括心跳检测/污点/容忍/中断等机制的实现...

    我是阳明

扫码关注云+社区

领取腾讯云代金券