Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
[分析] 这道题目看似简单,如果对题意和Java引用概念把握不好得话是写不对的。我的实现版本遇到有节点指向自身的case就挂,虽然知道问题所在却不知道如何修改好,看到网友的实现后豁然开朗,让我对引用的理解又加深了。使用HashMap,保存原节点和复制节点的映射,遇到节点指向自身时将该节点自身的引用加入到neighbors中而不要新建一个对象,好像是废话但自己当时怎么也想不到,练习练习再练习!
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
UndirectedGraphNode nodeClone = new UndirectedGraphNode(node.label);
LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
queue.offer(node);
map.put(node, nodeClone);
while (!queue.isEmpty()) {
UndirectedGraphNode curr = queue.poll();
List<UndirectedGraphNode> neighbors = curr.neighbors;
for (UndirectedGraphNode neigh : neighbors) {
if (!map.containsKey(neigh)) {
UndirectedGraphNode neighClone = new UndirectedGraphNode(neigh.label);
map.get(curr).neighbors.add(neighClone);
queue.offer(neigh);
map.put(neigh, neighClone);
} else {
map.get(curr).neighbors.add(map.get(neigh));
}
}
}
return nodeClone;
}
}
错误版本及fail的case
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
LinkedList<UndirectedGraphNode> queueClone = new LinkedList<UndirectedGraphNode>();
queue.offer(node);
queueClone.offer(clone);
HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
visited.add(node);
while (!queue.isEmpty()) {
UndirectedGraphNode curr = queue.poll();
UndirectedGraphNode currClone = queueClone.poll();
for (UndirectedGraphNode neigh : curr.neighbors) {
UndirectedGraphNode neighClone = new UndirectedGraphNode(neigh.label);
currClone.neighbors.add(neighClone);
if (visited.contains(neigh)) continue;
queue.offer(neigh);
queueClone.offer(neighClone);
visited.add(neigh);
}
}
return clone;
}
- 大小: 2.5 KB
分享到:
相关推荐
python python_leetcode题解之133_Clone_Graph
用java解决包含但不限于array/tree/graph等几种数据结构、分治/DP/backtrack等几种算法思想的题目,并取得平均题解runtime beats 80%的成绩。 每天打卡(估计很快失败)平均每天1题保本,2题赚翻。 项目构建: 根...
leetcode CloneGraph java 源代码
133.Clone_Graph_克隆图【LeetCode单题讲解系列】
Clone_Graph 组合_总和 Counting_Carry_Digits 平等的 First_Missing_Positive Generate_All_Parenthesis_2 实现_StrStr Largest_Distance_Between_Nodes_Of_A_Tree Largest_Rectangle_In_Histogram Least_C
leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目...graph:图论 greedy:贪心算法 recursion:递归算法 sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8
**1.19 Clone Graph (133)** - **问题描述**:给定一个无向图,对其进行深拷贝。 - **解题思路**: - 使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历整个图。 - 对于每个访问过的节点,创建一个副本,并将...
Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...
38. Clone Graph:深度复制一个图。 【栈】 39. Min Stack:设计一个栈,支持 push、pop、top 操作,并且在常数时间内得到栈的最小值。 40. Evaluate Reverse Polish Notation:计算后缀表达式。 41. Valid ...
杂项部分包括了一些不那么容易归类的问题,如螺旋矩阵(Spiral Matrix)、整数转罗马数字(Integer to Roman)、克隆图(Clone Graph)等。 **栈(Stack)** 栈是一种先进后出(FILO)的数据结构。 - 最小栈(Min ...
与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve
例如,"Clone Graph"题目中,通过DFS克隆一个无向图;"Shortest Path in Binary Matrix"则需要BFS寻找矩阵中最短路径。 总结,通过LeetCode的实践,我们可以提升JavaScript编程技巧,熟练掌握各种数据结构和算法,...
图形**** ****BFS class Solution { public Node cloneGraph ( Node node ) { if (node == null ) { return null ; } Map< Node> map = new HashMap<> (); Queue< Node> queue = new LinkedList<> (); queue ....
存储库会定期更新,因此请确保提取代码git pull组织这些问题按其来源的主要主题划分问题陈述在代码顶部被注释掉LeetCode问题被命名为leetcode_(问题编号)_(问题标题),并且仅提供Solution类其他问题仅通过标题...
`cloneGraph`函数的目的是接收一个`Node`对象并返回一个新的、完全独立的`Node`对象,所有节点及其连接关系都要被正确地复制。 解决方案是使用深度优先搜索策略。首先,创建一个空的`map_list`字典,用于存储原图中...
38. Clone Graph:复制一个无向图。 39. Min Stack:设计一个栈,支持获取栈内最小元素的操作。 40. Evaluate Reverse Polish Notation:计算后缀表达式的值。 41. Valid Parentheses:判断字符串是否为有效的括号...