前言
持续更新了
正文
问题来源
本问题来自leetcode上的133题。
问题描述
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
示例 1:
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
分析：
用一个map来记录原指针和新创建节点的一个映射关系，如果该节点已经创建了就直接返回，如果该节点没有创建，则创建该节点，并将它的neighbors递归获得。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Neighbors []*Node
* }
*/
var m map[*Node]*Node
func cloneGraph(node *Node) *Node {
if node == nil {
return nil
}
m = make(map[*Node]*Node)
return clone(node)
}
func clone(src *Node) *Node {
var ok bool
var n *Node
if n, ok = m[src]; !ok {
n = &Node{src.Val, make([]*Node, len(src.Neighbors))}
m[src] = n
} else {
return n
}
for i, v := range src.Neighbors {
n.Neighbors[i] = clone(v)
}
return n
}
官方解答
使用 HashMap 存储所有访问过的节点和克隆节点。HashMap 的 key 存储原始图的节点，value 存储克隆图中的对应节点。visited 用于防止陷入死循环，和获得克隆图的节点。
将第一个节点添加到队列。克隆第一个节点添加到名为 visited 的 HashMap 中。
BFS 遍历
从队列首部取出一个节点。
遍历该节点的所有邻接点。
如果某个邻接点已被访问，则该邻接点一定在 visited 中，那么从 visited 获得该邻接点。
否则，创建一个新的节点存储在 visited 中。
将克隆的邻接点添加到克隆图对应节点的邻接表中。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
// Hash map to save the visited node and it's respective clone
// as key and value respectively. This helps to avoid cycles.
HashMap<Node, Node> visited = new HashMap();
// Put the first node in the queue
LinkedList<Node> queue = new LinkedList<Node> ();
queue.add(node);
// Clone the node and put it in the visited dictionary.
visited.put(node, new Node(node.val, new ArrayList()));
// Start BFS traversal
while (!queue.isEmpty()) {
// Pop a node say "n" from the from the front of the queue.
Node n = queue.remove();
// Iterate through all the neighbors of the node "n"
for (Node neighbor: n.neighbors) {
if (!visited.containsKey(neighbor)) {
// Clone the neighbor and put in the visited, if not present already
visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
// Add the newly encountered node to the queue.
queue.add(neighbor);
}
// Add the clone of the neighbor to the neighbors of the clone node "n".
visited.get(n).neighbors.add(visited.get(neighbor));
}
}
// Return the clone of the node from visited.
return visited.get(node);
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
