資訊專欄INFORMATION COLUMN
摘要：我們只要保證，對(duì)于第一次遇到的圖節(jié)點(diǎn)，我們都會(huì)建立一個(gè)克隆節(jié)點(diǎn)，并在哈希表映射起來(lái)就行了。所以只要哈希表中有這個(gè)圖節(jié)點(diǎn)，就說(shuō)明我們之前已經(jīng)將該圖節(jié)點(diǎn)放入隊(duì)列了，就不需要再處理了。
Clone Graph
哈希表法 復(fù)雜度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 / \_/
時(shí)間 O(N) 空間 O(N)
思路廣度優(yōu)先搜索，同時(shí)用一個(gè)哈希表，將新舊節(jié)點(diǎn)映射起來(lái)。這樣我們第一次遍歷到的節(jié)點(diǎn)，我們會(huì)新建一個(gè)節(jié)點(diǎn)并映射到哈希表中。當(dāng)以后再遍歷到這個(gè)節(jié)點(diǎn)時(shí)，我們可以直接用哈希表取出它對(duì)應(yīng)的新節(jié)點(diǎn)。我們只要保證，對(duì)于第一次遇到的圖節(jié)點(diǎn)，我們都會(huì)建立一個(gè)克隆節(jié)點(diǎn)，并在哈希表映射起來(lái)就行了。
注意這里我們并不需要維護(hù)一個(gè)visited的集合，為什么呢？因?yàn)槊看挝覀冇龅揭粋€(gè)之前沒(méi)見(jiàn)過(guò)圖節(jié)點(diǎn)，我們都會(huì)給它建立一個(gè)克隆節(jié)點(diǎn)，然后在哈希表中映射起來(lái)，并把這個(gè)圖節(jié)點(diǎn)也放入隊(duì)列中。所以只要哈希表中有這個(gè)圖節(jié)點(diǎn)，就說(shuō)明我們之前已經(jīng)將該圖節(jié)點(diǎn)放入隊(duì)列了，就不需要再處理了。不過(guò)還是要把該圖節(jié)點(diǎn)的克隆節(jié)點(diǎn)放入父克隆節(jié)點(diǎn)的鄰居中。
代碼public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
Queue q = new LinkedList();
Map map = new HashMap();
UndirectedGraphNode root = new UndirectedGraphNode(node.label);
map.put(node, root);
q.offer(node);
while(!q.isEmpty()){
UndirectedGraphNode curr = q.poll();
// 將curr舊節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都加入curr的新節(jié)點(diǎn)
for(UndirectedGraphNode oldNeighbor : curr.neighbors){
// 判斷是否已經(jīng)生成過(guò)該鄰居節(jié)點(diǎn)的新節(jié)點(diǎn)
if(!map.containsKey(oldNeighbor)){
// 如果是第一次生成該新節(jié)點(diǎn)，將其加入隊(duì)列中
map.put(oldNeighbor, new UndirectedGraphNode(oldNeighbor.label));
q.offer(oldNeighbor);
}
// 將新鄰居加入新curr節(jié)點(diǎn)的neighbors中
map.get(curr).neighbors.add(map.get(oldNeighbor));
}
}
return root;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64503.html
摘要：開(kāi)始看這道題目的時(shí)候，沒(méi)有看懂和的作用。然后對(duì)這個(gè)放入的結(jié)點(diǎn)開(kāi)始操作遍歷的所有，當(dāng)前遍歷到的的叫做。當(dāng)完成，則中沒(méi)有新的結(jié)點(diǎn)了，退出循環(huán)。返回在中更新過(guò)的，結(jié)束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...
摘要：解題思路涉及到圖的遍歷無(wú)非就是深度優(yōu)先搜索廣度優(yōu)先搜索，可以先看前幾日的這篇文章就需要借助隊(duì)列實(shí)現(xiàn)，可以借助棧也可以直接用遞歸實(shí)現(xiàn)。 題目： 給定無(wú)向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克隆）。圖中的每個(gè)節(jié)點(diǎn)都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。 Given a reference of a node in a connected undirec...
摘要：遍歷路徑，找到所有可以到達(dá)終點(diǎn)節(jié)點(diǎn)的路徑就是結(jié)果。提示中說(shuō)保證輸入為有向無(wú)環(huán)圖，所以我們可以認(rèn)為節(jié)點(diǎn)間一定有著某種排列的順序，從頭到尾怎樣可以有最多的路徑呢，那就是在保證沒(méi)有環(huán)路的情況下，所有節(jié)點(diǎn)都盡可能多的連接著其他節(jié)點(diǎn)。 ...
摘要：拓?fù)渑判驈?fù)雜度時(shí)間空間思路首先簡(jiǎn)單介紹一下拓?fù)渑判?，這是一個(gè)能夠找出有向無(wú)環(huán)圖順序的一個(gè)方法假設(shè)我們有條邊，先將每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后，我們開(kāi)始拓?fù)渑判?，從?jì)數(shù)器為的字母開(kāi)始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...
Course Schedule I There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is e...
閱讀 1786·2021-11-22 14:45
閱讀 1337·2021-11-17 09:33
閱讀 3486·2021-09-02 09:48
閱讀 1157·2019-08-30 15:54
閱讀 2896·2019-08-30 15:53
閱讀 2699·2019-08-30 12:54
閱讀 2392·2019-08-29 12:37
閱讀 2547·2019-08-26 13:58
