【Leetcode】133.克隆图
【Leetcode】133.克隆图
Leetcode名企之路
发布于 2019-06-18 17:09:18
发布于 2019-06-18 17:09:18
题目
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
示例：
img
输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。提示：
- 节点数介于 1 到 100 之间。
- 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
- 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
- 必须将给定节点的拷贝作为对克隆图的引用返回。
题解
这道题目是图的遍历，节点遍历我们很熟悉，要么dfs，要么dfs。关键点是：图的边怎么复制。为了复制两个节点之间边的关系，我们用一个map去记录原节点和新节点之间的对应关系，这样遍历节点的的时候我们就可以通过map 查到复制节点的，把他们的边复制上。我们先采用bfs的方式来复制图。
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(node);
Node copyNode = new Node();
copyNode.val = node.val;
map.put(node, copyNode);
while (!queue.isEmpty()) {
Node current = queue.poll();
if (current.neighbors == null) {
continue;
}
if (map.get(current).neighbors == null) {
map.get(current).neighbors = new LinkedList<>();
}
List<Node> neighbors = current.neighbors;
List<Node> copiedNeighbors = new LinkedList<>();
for (Node neighbor : neighbors) {
if (!map.containsKey(neighbor)) {
queue.add(neighbor);
Node tmp = new Node();
tmp.val = neighbor.val;
map.put(neighbor, tmp);
}
map.get(current).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}采用dfs的递归方式来复制图。
class Solution {
public Node cloneGraph(Node node) {
Map<Node, Node> resNode2CopyNode = new HashMap<>();
return helper(node, resNode2CopyNode);
}
public Node helper(Node node, Map<Node, Node> resNode2CopyNode) {
if (node == null) return null;
if (!resNode2CopyNode.containsKey(node)) {
Node tmp = new Node();
tmp.val = node.val;
resNode2CopyNode.put(node, tmp);
}
Node copy = resNode2CopyNode.get(node);
if (node.neighbors == null) {
return copy;
}
copy.neighbors = new LinkedList<>();
List<Node> neighbors = node.neighbors;
for (Node neighbor : neighbors) {
Node copyNeighbor = null;
if (resNode2CopyNode.containsKey(neighbor)) {
copyNeighbor = resNode2CopyNode.get(neighbor);
} else {
copyNeighbor = helper(neighbor, resNode2CopyNode);
}
copy.neighbors.add(copyNeighbor);
}
return copy;
}
}采用dfs迭代的方式来解。
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> resNode2CopyNode = new HashMap<>();
Stack<Node> stack = new Stack<>();
stack.push(node);
Node copy = new Node();
copy.val = node.val;
resNode2CopyNode.put(node, copy);
while (!stack.isEmpty()) {
Node current = stack.pop();
List<Node> neighbors = current.neighbors;
if (neighbors == null) {
continue;
}
Node copyNode = resNode2CopyNode.get(current);
if (copyNode.neighbors == null) {
copyNode.neighbors = new LinkedList<>();
}
for (Node neighbor : neighbors) {
Node copyNeighbor = null;
if (resNode2CopyNode.containsKey(neighbor)) {
copyNeighbor = resNode2CopyNode.get(neighbor);
} else {
copyNeighbor = new Node();
copyNeighbor.val = neighbor.val;
resNode2CopyNode.put(neighbor, copyNeighbor);
stack.push(neighbor);
}
copyNode.neighbors.add(copyNeighbor);
}
}
return copy;
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录