`
huntfor
  • 浏览: 201077 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Clone Graph

 
阅读更多

新博文地址:[leecode]Clone Graph

Clone Graph

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
             / \
             \_/

这道题刚开始都木有看懂= =//,还纳闷,参数只给了一个点node,题目怎么说复制graph呢,后来才反应过来,题中参数给的其实是一个连通分量啊。。

简单的做一下描述:复制一个有向图的连通分量

BFS和DFS应该都可以,我用的BFS,题目没啥难度,就是有一点需要注意->图中两点之间的边,可能有多条,比如#2,3,3,表示点2,到点3有两条路,更甚者#5,5,5.....在现实中的含义可能是你原地转小圈转大圈的区别吧= =//

弄懂了题意之后,对BFS做一下适当的变形,配合hashMap和set,没啥难度

代码如下:

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if(node == null || node.neighbors == null || node.neighbors.size() == 0){
			return node == null ? node : new UndirectedGraphNode(node.label);
		}
		Queue<UndirectedGraphNode> q = new ArrayDeque<UndirectedGraphNode>();
		q.offer(node);
		Map<Integer,UndirectedGraphNode> hash = new HashMap<Integer,UndirectedGraphNode>();
		Set<Integer> processed = new HashSet<Integer>();
		UndirectedGraphNode nodeClone = new UndirectedGraphNode(node.label);
		hash.put(node.label, nodeClone);
		while(!q.isEmpty()){
			UndirectedGraphNode tem = q.poll();
			processed.add(tem.label);
			UndirectedGraphNode temClone = hash.containsKey(tem.label) ? hash.get(tem.label) : new UndirectedGraphNode(tem.label);
			for(UndirectedGraphNode neighbor : tem.neighbors){
				if(!processed.contains(neighbor.label)){
					boolean exist = false;
					for(UndirectedGraphNode n : q){
						if(n.label == neighbor.label){
							exist = true;
							break;
						}
					}
					if(!exist) q.offer(neighbor);
				}
				if(!hash.containsKey(neighbor.label)){
					UndirectedGraphNode neighborClone = new UndirectedGraphNode(neighbor.label);
					temClone.neighbors.add(neighborClone);
					hash.put(neighbor.label, neighborClone);
				}else{
					temClone.neighbors.add(hash.get(neighbor.label));
				}
			}
		}
		return nodeClone;
    }

 

分享到:
评论

相关推荐

    CloneGraph

    leetcode CloneGraph java 源代码

    133.Clone Graph 克隆图【LeetCode单题讲解系列】

    133.Clone_Graph_克隆图【LeetCode单题讲解系列】

    python-leetcode题解之133-Clone-Graph

    python python_leetcode题解之133_Clone_Graph

    js-leetcode题解之133-clone-graph.js

    javascript js_leetcode题解之133-clone-graph.js

    Leetcode book刷题必备

    38. Clone Graph:深度复制一个图。 【栈】 39. Min Stack:设计一个栈,支持 push、pop、top 操作,并且在常数时间内得到栈的最小值。 40. Evaluate Reverse Polish Notation:计算后缀表达式。 41. Valid ...

    Leetcode答案(c++版)

    **1.19 Clone Graph (133)** - **问题描述**:给定一个无向图,对其进行深拷贝。 - **解题思路**: - 使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历整个图。 - 对于每个访问过的节点,创建一个副本,并将...

    leetcode分类-leetcode-solution:leetcode-解决方案

    用java解决包含但不限于array/tree/graph等几种数据结构、分治/DP/backtrack等几种算法思想的题目,并取得平均题解runtime beats 80%的成绩。 每天打卡(估计很快失败)平均每天1题保本,2题赚翻。 项目构建: 根...

    leetcode java

    杂项部分包括了一些不那么容易归类的问题,如螺旋矩阵(Spiral Matrix)、整数转罗马数字(Integer to Roman)、克隆图(Clone Graph)等。 **栈(Stack)** 栈是一种先进后出(FILO)的数据结构。 - 最小栈(Min ...

    leetcode分类-leetcode:leetcode

    leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目...graph:图论 greedy:贪心算法 recursion:递归算法 sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8

    leetcode同类骰子-Algorithms:LeetCode,GeeksforGeeks

    Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...

    algorithms:只是个菜鸟。这个项目是在空闲时间编写的。我会不定期更新。希望与您分享一些东西〜

    与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve

    LeetCode

    例如,"Clone Graph"题目中,通过DFS克隆一个无向图;"Shortest Path in Binary Matrix"则需要BFS寻找矩阵中最短路径。 总结,通过LeetCode的实践,我们可以提升JavaScript编程技巧,熟练掌握各种数据结构和算法,...

    Leetcode注意

    图形**** ****BFS class Solution { public Node cloneGraph ( Node node ) { if (node == null ) { return null ; } Map&lt; Node&gt; map = new HashMap&lt;&gt; (); Queue&lt; Node&gt; queue = new LinkedList&lt;&gt; (); queue ....

    股票买卖最佳时机leetcode-Java-Projects:Java项目和面试问题的存储库,用于编码面试的练习

    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

    克隆图(python map+dfs)1

    `cloneGraph`函数的目的是接收一个`Node`对象并返回一个新的、完全独立的`Node`对象,所有节点及其连接关系都要被正确地复制。 解决方案是使用深度优先搜索策略。首先,创建一个空的`map_list`字典,用于存储原图中...

    常见算法题答案及解析

    38. Clone Graph:复制一个无向图。 39. Min Stack:设计一个栈,支持获取栈内最小元素的操作。 40. Evaluate Reverse Polish Notation:计算后缀表达式的值。 41. Valid Parentheses:判断字符串是否为有效的括号...

    CPP-JAVA-DSA:使用C ++和Java解决了来自不同编码网站的面试CC问题

    存储库会定期更新,因此请确保提取代码git pull组织这些问题按其来源的主要主题划分问题陈述在代码顶部被注释掉LeetCode问题被命名为leetcode_(问题编号)_(问题标题),并且仅提供Solution类其他问题仅通过标题...

Global site tag (gtag.js) - Google Analytics