力扣(LeetCode)133

Steve_Wang_ 發(fā)布于2019-08-19 11:39 / 3176人閱讀

摘要：提示節(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 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;
        
    }
}