原题
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
示例:
输入:
{"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 。
解法
思想
Hashmap维持原图节点和克隆节点的对应关系，如果给邻居节点赋值的时候不存在对应的克隆节点则获取对应的克隆节点，直到有一个节点的邻居节点的克隆节点都存在于map中。
代码
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
//hashmap维持原图和克隆图之间节点的对应关系
Map<Node, Node> lookup;
public Node cloneGraph(Node node) {
lookup = new HashMap<>();
return dfs(node);
}
//每一次dfs操作实际上就是确保存在node节点的复制节点
private Node dfs(Node node) {
if (node == null) return null;
//存在对应的克隆节点直接返回
if (lookup.containsKey(node)) return lookup.get(node);
//先创建对应的克隆节点，邻居列表在递归返回的时候添加。
Node clone = new Node(node.val, new ArrayList<>());
lookup.put(node, clone);
for (Node n : node.neighbors)
//添加n的克隆节点
clone.neighbors.add(dfs(n));
return clone;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode133-%e5%85%8b%e9%9a%86%e5%9b%be/
相关推荐
-
leetcode374-猜数字大小
原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...
-
leetcode701-二叉搜索树中的插入操作
原题 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意，可能存在多种有效的插入方式，只...
-
leetcode380-常数时间插入、删除和获取随机元素
原题 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。 insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 v...
-
leetcode62-不同路径
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
-
leetcode1111-有效括号的嵌套深度
原题 有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一： 空字符串 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串 嵌套，可以...
-
leetcode103-二叉树的锯齿形层次遍历
原题 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如:给定二叉树: [3,9,20,null,nul...
-
leetcode347-前K个高频元素
原题 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1： 输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例2： 输入： n...
-
leetcode1103-分糖果II
原题 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类...
-
leetcode123-买卖股票的最佳时机III
原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...
-
leetcode153-寻找旋转排序数组中的最小值
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...