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