C++实现LeetCode(133.克隆无向图)

[LeetCode] 133. Clone Graph 克隆无向图

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

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}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

  1. The number of nodes will be between 1 and 100.
  2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
  3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
  4. You must return the copy of the given node as a reference to the cloned graph.

这道无向图的复制问题和之前的 Copy List with Random Pointer 有些类似，那道题的难点是如何处理每个结点的随机指针，这道题目的难点在于如何处理每个结点的 neighbors，由于在深度拷贝每一个结点后，还要将其所有 neighbors 放到一个 vector 中，而如何避免重复拷贝呢？这道题好就好在所有结点值不同，所以我们可以使用 HashMap 来对应原图中的结点和新生成的克隆图中的结点。对于图的遍历的两大基本方法是深度优先搜索 DFS 和广度优先搜索 BFS，这里我们先使用深度优先搜索DFS来解答此题，在递归函数中，首先判空，然后再看当前的结点是否已经被克隆过了，若在 HashMap 中存在，则直接返回其映射结点。否则就克隆当前结点，并在 HashMap 中建立映射，然后遍历当前结点的所有 neihbor 结点，调用递归函数并且加到克隆结点的 neighbors 数组中即可，代码如下：

解法一：

class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> m;
        return helper(node, m);
    }
    Node* helper(Node* node, unordered_map<Node*, Node*>& m) {
        if (!node) return NULL;
        if (m.count(node)) return m[node];
        Node *clone = new Node(node->val);
        m[node] = clone;
        for (Node *neighbor : node->neighbors) {
            clone->neighbors.push_back(helper(neighbor, m));
        }
        return clone;
    }
};

我们也可以使用 BFS 来遍历图，使用队列 queue 进行辅助，还是需要一个 HashMap 来建立原图结点和克隆结点之间的映射。先克隆当前结点，然后建立映射，并加入 queue 中，进行 while 循环。在循环中，取出队首结点，遍历其所有 neighbor 结点，若不在 HashMap 中，我们根据 neigbor 结点值克隆一个新 neighbor 结点，建立映射，并且排入 queue 中。然后将 neighbor 结点在 HashMap 中的映射结点加入到克隆结点的 neighbors 数组中即可，参见代码如下：

解法二：

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        unordered_map<Node*, Node*> m;
        queue<Node*> q{{node}};
        Node *clone = new Node(node->val);
        m[node] = clone;
        while (!q.empty()) {
            Node *t = q.front(); q.pop();
            for (Node *neighbor : t->neighbors) {
                if (!m.count(neighbor)) {
                    m[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                m[t]->neighbors.push_back(m[neighbor]);
            }
        }
        return clone;
    }
};

类似题目：

Copy List with Random Pointer

参考资料：

https://leetcode.com/problems/clone-graph/

https://leetcode.com/problems/clone-graph/discuss/42313/C%2B%2B-BFSDFS

https://leetcode.com/problems/clone-graph/discuss/42309/Depth-First-Simple-Java-Solution

到此这篇关于C++实现LeetCode(133.克隆无向图)的文章就介绍到这了,更多相关C++实现克隆无向图内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(127.词语阶梯)

    [LeetCode] 127.Word Ladder 词语阶梯 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transforme

  • C++实现LeetCode(128.求最长连续序列)

    [LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl

  • C++实现LeetCode(200.岛屿的数量)

    [LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four

  • C++实现LeetCode(134.加油站问题)

    [LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1)

  • C++实现LeetCode(129.求根到叶节点数字之和)

    [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum

  • C++实现LeetCode(130.包围区域)

    [LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O

  • C++验证LeetCode包围区域的DFS方法

    验证LeetCode Surrounded Regions 包围区域的DFS方法 在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<

  • C++实现LeetCode(126.词语阶梯之二)

    [LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed

  • C++实现LeetCode(133.克隆无向图)

    C++实现LeetCode(133.克隆无向图)

    [LeetCode] 133. Clone Graph 克隆无向图 Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":

  • C++实现LeetCode(207.课程清单)

    [LeetCode] 207. Course Schedule 课程清单 There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given

  • vmware虚拟机怎么克隆 VMware11.0.0虚拟机克隆

    vmware虚拟机怎么克隆 VMware11.0.0虚拟机克隆

    开发中需要用到多个虚拟机进行实验.重新安装过程又太繁琐,通过vmware虚拟机自带软件能够很好的快速克隆出完全相同的系统.下面会为大家讲解关于vmware虚拟机怎么克隆,我所用的VMware版本是11.0.0. 1.在Vmware Workstation主面板左侧的我的计算机节点下选一个已安装过的虚拟机,我自己的是Hadoop-Senior02 2.在Hadoop-Senior02虚拟机上通过鼠标右键菜单依次选择,管理->克隆,点击克隆 3.一直下一步,直到出现克隆类型面板,选择创建完整的克隆,

  • VMware 克隆多台Linux机器并配置IP的方法

    VMware 克隆多台Linux机器并配置IP的方法

    1.查看并分配虚拟网络 我们首先要知道 VMware 三种网络模式的区别. ①.Bridged(桥接模式):就是将主机网卡与虚拟机虚拟的网卡利用虚拟网桥进行通信.在桥接的作用下,类似于把物理主机虚拟为一个交换机,所有桥接设置的虚拟机连接到这个交换机的一个接口上,物理主机也同样插在这个交换机当中,所以所有桥接下的网卡与网卡都是交换模式的,相互可以访问而不干扰.在桥接模式下,虚拟机ip地址需要与主机在同一个网段,如果需要联网,则网关与DNS需要与主机网卡一致. ②.NAT(网络地址转换模式):主机网

  • 在VMware下快速克隆多个Linux环境的方法教程

    在VMware下快速克隆多个Linux环境的方法教程

    为什么要克隆多个 Linux 系统? 因为要玩阿.其实也不是了,就是为了折腾嘛,玩个数据库主从啦.缓存集群啦.分布式消息集群啦.分布式各类服务啦,你要模拟几乎接近真实的环境,就必须要有多台机器,你想要有多台机器只有两种方式:买买买和装虚拟机. 你现在要模拟三台机器下实现分布式服务,你要怎么装环境? 当你在 VMware 里装好了一个 Linux 系统后,当然你可以选择再装下一个和下下一个,这没啥问题!不过,你就需要在每台机器上安装各种软件,如:JDK.Tomcat.Nginx啦.我这有一个极其方

  • JS对象的深度克隆方法示例

    本文实例讲述了JS对象的深度克隆方法.分享给大家供大家参考,具体如下: js中创建的对象指向内存,所以在开发过程中,往往修改了一个对象的属性,会影响另外一个对象. 尤其是在angular框架中,dom是由数据驱动的,在增删改查对象的操作中,对象属性的继承关系是很让人头痛的! 我之前遇到的问题就是,在编辑页面,操作了对象数据,影响到了展示数据的展现! 我整理了两种深度克隆对象的方法,供大家参考! 首先var 一个假数据 复制代码 代码如下: var schedule = {"status"

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • Powershell实现克隆NTFS文件系统权限

    支持所有版本. 下面有一段简单的代码获取某个文件夹或程序的权限赋给一个其它对象.注意路径必须都是存在: 复制代码 代码如下: $FolderToCopyFrom = 'C:\folder1' $FolderToCopyTo = 'C:\folder2'   $securityDescriptor = Get-Acl -Path $FolderToCopyFrom Set-Acl -Path $FolderToCopyTo -AclObject $securityDescriptor 克隆安全描述

  • JavaScript 深层克隆对象详解及实例

    JavaScript 深层克隆对象详解及实例

     JavaScript 深层克隆对象 今天做项目,有个需求需要用到深层克隆对象,并且要求在原型链上编程 于是心血来潮索性来复习一下这个知识点,在网上找了相应的知识, 克隆对象,这名词看着高大上,其实也没什么,便是拷贝一个长的一模一样的对象 也许有初学的小伙伴在想,那还不简单么,so easy var obj1 = {name: 'payen'}; var obj2 = obj1; 这可并不是克隆对象,obj1和obj2根本就是同一个对象, 他俩指向同一个内存地址空间,拿到了同样的一个小房子 这是

  • js克隆对象、数组的常用方法介绍

    Ext的两种克隆的方法: 可以克隆对象.数据等:var newJson = Ext.clone(json); 只能克隆数组:var newJson = Ext.Array.clone(json); JQuery的方法: 深复制[可以迭代]:var newJson = jQuery.extend(true,{}, json); 浅复制[不能迭代]:var newJson = jQuery.extend({}, json); var newJson = $.map(json,function (n)

随机推荐