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