- 浏览: 173448 次
- 性别:
- 来自: 济南
文章分类
最新评论
之所以把这道题单独拿出来,是因为通过它我们可以了解到图的结构,以及如何处理,我们分别用递归,广搜和深搜来完成这道题。
Clone Graph
复制一个无向图,图中每个节点都有一个label和一个neighbors集合。
解决图的题,因为图中存在环,我们要判断哪些点已经访问过了,做上标记,以防止进入死循环。这里我们用哈希函数来判断一个顶点是否被访问过,如果没被访问过就加入到哈希表中。
首先我们通过广搜来完成它。广搜用到队列,代码如下:
深度搜索用到堆栈,代码如下:
递归实现:
Clone Graph
复制一个无向图,图中每个节点都有一个label和一个neighbors集合。
解决图的题,因为图中存在环,我们要判断哪些点已经访问过了,做上标记,以防止进入死循环。这里我们用哈希函数来判断一个顶点是否被访问过,如果没被访问过就加入到哈希表中。
首先我们通过广搜来完成它。广搜用到队列,代码如下:
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); if(node == null) return null; UndirectedGraphNode copy = new UndirectedGraphNode(node.label); hm.put(node,copy); queue.offer(node); while(!queue.isEmpty()) { UndirectedGraphNode cur = queue.poll(); for(UndirectedGraphNode neighbor : cur.neighbors) { if(!hm.containsKey(neighbor)) { copy = new UndirectedGraphNode(neighbor.label); hm.put(neighbor, copy); queue.offer(neighbor); } hm.get(cur).neighbors.add(hm.get(neighbor)); } } return hm.get(node); } }
深度搜索用到堆栈,代码如下:
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>(); if(node == null) return null; stack.push(node); UndirectedGraphNode copy = new UndirectedGraphNode(node.label); hm.put(node,copy); while(!stack.isEmpty()) { UndirectedGraphNode cur = stack.pop(); for(UndirectedGraphNode neighbor : cur.neighbors) { if(!hm.containsKey(neighbor)) { copy = new UndirectedGraphNode(neighbor.label); hm.put(neighbor, copy); stack.push(neighbor); } hm.get(cur).neighbors.add(hm.get(neighbor)); } } return hm.get(node); } }
递归实现:
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); return DFS(hm, node); } private UndirectedGraphNode DFS(HashMap<UndirectedGraphNode, UndirectedGraphNode> hm, UndirectedGraphNode node) { if(node == null) return null; UndirectedGraphNode copy = new UndirectedGraphNode(node.label); hm.put(node, copy); for(UndirectedGraphNode neighbor : node.neighbors) { if(!hm.containsKey(neighbor)) { UndirectedGraphNode neighborcopy = DFS(hm, neighbor); } copy.neighbors.add(hm.get(neighbor)); } return copy; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 333Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 532Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 735You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
leetcode CloneGraph java 源代码
https://www.lintcode.com/problem/clone-graph/description Deep copy一个图。图以邻接表方式存储。 思路是,先从给定的顶点出发,搜索到图中的所有的顶点,然后为每个顶点创建一份拷贝;接着,遍历原图的顶点,每...
133.Clone_Graph_克隆图【LeetCode单题讲解系列】
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 ...
与大家分享我学习算法的一些经历。这个项目不定期更新。数组/链表:树相关:AVLTree 平衡二叉搜索树...BFSGraph 图BFS模板Dijkstra 寻求最短路SwimmingCrossSea 漂洋过海CloneGraph (leetcode 133)字符串相关:Reve
Clone Graph, medium --- 类似于#138 207,课程表,中等 210 课程表 II,中等 261,图有效树,中等 310,最小高度树,中等 323,无向图中连通分量的数量,中等 444,序列重建,中 第二周——堆 215,数组中的第 K 个...
We propose a new variant of LSH scheme and incorporate it with graph matching to address these challenges. We implement an integrated assembly clone search engine called Kam1n0. It is the first clone...
If you clone the whole project, main app is a sample app that you can run and see simplegraph functionality in action. Why this library is out there? Well, I've spent too much time looking for library...
LDBC SNB在Janusgraph上... 解压缩 在配置了后端存储的情况下运行Janusgraph,请参阅bin/janusgraph start|status|stop|clean# bin/gremlin-server.sh #need configure backend storage克隆并构建git clone git@github....
$ sudo apt install libpcre2-dev libxml2-dev签出存储库并初始化所有子模块 $ git clone https://github.com/kuopinghsu/callgraph-gen.git$ cd callgraph-gen$ git submodule update --init --recursive建造 $ ...
git clone --recursive https://github.com/andydbc/unity-shadergraph-sandbox.git 现有存储库可以手动更新: git submodule init git submodule update 例子 溶解 火 全息图 像素化 香椿 简单标志 要求 ...
依存关系本征3.3或更高版本Ceres Solver 1.12.0或更高版本Gflags 2.2.0或更高版本带有matplotlib的Python建造$ git clone https://github.com/shinsumicco/pose-graph-optimization.git$ cd pose-graph-optimization...
$ git clone https://github.com/KKhanda/graph-db.git 生成并运行应用程序 $ go build ./cmd/graph-db/ $ ./graph-db 运行测试 $ go test ./... -cover API说明 API使用示例附在“ main.go”文件中。
git clone https://github.com/VirusTotal/vt_graph_apicd vt_graph_apipip install . --user验证安装>> > import vt_graph_api>> > vt_graph_api . __version__X . X . X文献资料有关如何使用vt_graph_api的更多...
$ git clone https://github.com/danini/graph-cut-ransac$ cd build$ cmake ..$ make安装Python包并编译C ++ python3 ./setup.py install 或者pip3 install -e .示例项目要构建显示基本矩阵,单应性和基本矩阵
图形**** ****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 clone https://github.com/kadukeitor/keep-graph.git 2.移至项目 cd keep-graph 3.安装依赖项 npm install 4.创建配置文件 cp .env.example .env 4.1。 当前配置 REACT_APP_GRAPHQL_ENDPOINT_SIMPLE=...
# clone project git clone https://github.com/YourGithubName/your-repo-name cd your-repo-name # optionally create conda environment conda update conda conda env create -f conda_env.yaml -n your_env_...
npm的软件包依赖图 该项目呈现npm软件包的依赖关系图。 它使用获取包元数据,使用绘制图形,使用进行... $ git clone https://github.com/TypeFox/npm-dependency-graph.git $ cd npm-dependency-graph $ yarn 作为
git clone https://github.com/rocurley/Nations-Graph.git cd Nations-Graph cabal sandbox init cabal install --only-dependencies 要下载图形: #the download command requres a maximum number of pages to ...