看到克隆图,自然想到遍历所有节点的算法,DFS/BFS改造下就可以了
本题中map用来保存已复制的节点(关系没有复制),同时也起到一个标记节点已访问过的作用。
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { private HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();//已复制过的节点 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { // Note: The Solution object is instantiated only once and is reused by each test case. map.clear(); return clone(node); } //dfs public UndirectedGraphNode clone(UndirectedGraphNode node){ if(node == null) return null; UndirectedGraphNode clonedNode = new UndirectedGraphNode(node.label); map.put(node,clonedNode); if(node.neighbors == null||node.neighbors.size() == 0) { return clonedNode; } for(UndirectedGraphNode unode:node.neighbors){ UndirectedGraphNode cloned = map.get(unode); if(cloned == null){ UndirectedGraphNode cloneNeighborNode = clone(unode); clonedNode.neighbors.add(cloneNeighborNode); }else{ clonedNode.neighbors.add(cloned); } } return clonedNode; } }
相关推荐
leetcode CloneGraph java 源代码
133.Clone_Graph_克隆图【LeetCode单题讲解系列】
用java解决包含但不限于array/tree/graph等几种数据结构、分治/DP/backtrack等几种算法思想的题目,并取得平均题解runtime beats 80%的成绩。 每天打卡(估计很快失败)平均每天1题保本,2题赚翻。 项目构建: 根...
leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目...graph:图论 greedy:贪心算法 recursion:递归算法 sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8
Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...
与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve
图形**** ****BFS class Solution { public Node cloneGraph ( Node node ) { if (node == null ) { return null ; } Map< Node> map = new HashMap<> (); Queue< Node> queue = new LinkedList<> (); queue ....
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
Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single Number II Single Number III Power of Two Missing Number Maximum Product of Word Lengths Bitwise ...
存储库会定期更新,因此请确保提取代码git pull组织这些问题按其来源的主要主题划分问题陈述在代码顶部被注释掉LeetCode问题被命名为leetcode_(问题编号)_(问题标题),并且仅提供Solution类其他问题仅通过标题...