資訊專欄INFORMATION COLUMN
摘要：提示節(jié)點(diǎn)數(shù)介于到之間。無向圖是一個(gè)簡(jiǎn)單圖，這意味著圖中沒有重復(fù)的邊，也沒有自環(huán)。必須將給定節(jié)點(diǎn)的拷貝作為對(duì)克隆圖的引用返回。這一題的做法是，使用一個(gè)來記錄，原和新的對(duì)應(yīng)關(guān)系。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定無向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克?。?。圖中的每個(gè)節(jié)點(diǎn)都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。
提示：
節(jié)點(diǎn)數(shù)介于 1 到 100 之間。
無向圖是一個(gè)簡(jiǎn)單圖，這意味著圖中沒有重復(fù)的邊，也沒有自環(huán)。
由于圖是無向的，如果節(jié)點(diǎn) p 是節(jié)點(diǎn) q 的鄰居，那么節(jié)點(diǎn) q 也必須是節(jié)點(diǎn) p 的鄰居。
必須將給定節(jié)點(diǎn)的拷貝作為對(duì)克隆圖的引用返回。
解答：
首先解釋一下，深拷貝的意思是，一個(gè)節(jié)點(diǎn)，若對(duì)它進(jìn)行深拷貝，那么必然生成一個(gè)新的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的所有的屬性值和原節(jié)點(diǎn)相同，但是這兩個(gè)節(jié)點(diǎn)在內(nèi)存中是兩個(gè)不同的對(duì)象，這樣稱之為深拷貝。
這一題的做法是，使用一個(gè)hashmap來記錄，原node 和 新node的對(duì)應(yīng)關(guān)系。
若原node已經(jīng)作為key存在于hashmap里，那么說明它的拷貝(新node)也
已經(jīng)存在，那么直接獲得它的拷貝，否則，就要為這個(gè)node生成新的拷貝
然后，把拷貝放入hashmap中，并且使得拷貝(新node)的鄰接鏈表添加原node的鄰接鏈表里元素的拷貝。
話比較繞，看代碼就懂了?。。?/p>
java ac代碼：
/*
// Definition for a Node.
class Node {
public int val;
public List neighbors;
public Node() {}
public Node(int _val,List _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
HashMapmap = new HashMap();
public Node cloneGraph(Node node) {
if(node == null)return null;
if(map.containsKey(node))
return map.get(node);
Node newnode = new Node(node.val,null);
map.put(node,newnode);
if(node.neighbors != null){
newnode.neighbors = new ArrayList();
for(Node nn:node.neighbors)
newnode.neighbors.add(cloneGraph(nn));
}
return newnode;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77624.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹特征的無向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁(yè)：應(yīng)無所住而生...
摘要：對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1074·2021-11-12 10:34
閱讀 999·2021-09-30 09:56
閱讀 676·2019-08-30 15:54
閱讀 2610·2019-08-30 11:14
閱讀 1476·2019-08-29 16:44
閱讀 3215·2019-08-29 16:35
閱讀 2500·2019-08-29 16:22
閱讀 2453·2019-08-29 15:39
