三刷 05/2022
Version #1 BFS (worse version - 2 passes)
写了一个比较冗余的版本
先BFS整个图clone nodes
再iterate hashmap clone edges
其实可以在BFS的时候同时clone nodes and edges
看下一个version
Time O(M + N) -> M is #edges, N is #nodes
Space O(N)
Runtime: 46 ms, faster than 22.53% of Java online submissions for Clone Graph.
Memory Usage: 43 MB, less than 63.60% of Java online submissions for Clone Graph.
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
// key-original node, value-cloned new node
Map<Node, Node> map = new HashMap<>();
Queue<Node> que = new ArrayDeque<>();
que.offer(node);
while (!que.isEmpty()) {
Node curr = que.poll();
map.put(curr, new Node(curr.val));
for (Node neighbor : curr.neighbors) {
if (map.containsKey(neighbor)) {
continue;
}
que.offer(neighbor);
}
}
for (Map.Entry<Node, Node> entry : map.entrySet()) {
for (Node neighbor : entry.getKey().neighbors) {
entry.getValue().neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}
Version #2 BFS (better - 1 pass)
Time O(M + N) -> M is #edges, N is #nodes
Space O(N)
Runtime: 36 ms, faster than 53.70% of Java online submissions for Clone Graph.
Memory Usage: 43.9 MB, less than 11.05% of Java online submissions for Clone Graph.
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
// key-original node, value-new node
Map<Node, Node> map = new HashMap<>();
// Create cloned node before added to que
// Add neighbors when polled from the que
Queue<Node> que = new ArrayDeque<>();
que.offer(node);
map.put(node, new Node(node.val));
while (!que.isEmpty()) {
Node curr = que.poll();
Node copiedCurr = map.get(curr);
for (Node neighbor : curr.neighbors) {
if (!map.containsKey(neighbor)) {
map.put(neighbor, new Node(neighbor.val));
que.offer(neighbor);
}
copiedCurr.neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}
Version #3 DFS
Might cause stack overflow
Time O(M + N) -> M is #edges, N is #nodes
Space O(N)
class Solution {
public Node cloneGraph(Node node) {
// key-original node, value-cloned new node
return dfs(node, new HashMap<>());
}
private Node dfs(Node node, Map<Node, Node> visited) {
if (node == null) {
return null;
}
if (visited.containsKey(node)) {
return visited.get(node);
}
Node copiedNode = new Node(node.val);
visited.put(node, copiedNode);
for (Node neighbor : node.neighbors) {
copiedNode.neighbors.add(dfs(neighbor, visited));
}
return copiedNode;
}
}
一刷
Version #1 BFS/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
50.64 %
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return node;
Queue<UndirectedGraphNode> que= new LinkedList<>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
que.add(node);
map.put(node, new UndirectedGraphNode(node.label));
while (!que.isEmpty()) {
UndirectedGraphNode curr = que.poll();
for (UndirectedGraphNode neighbor : curr.neighbors) {
if (!map.containsKey(neighbor)) {
que.add(neighbor);
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
}
map.get(curr).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}
Version #2 DFS
二刷
写了一个bug
因为点可以自己指向自己
一开始先add neighbors然后再map.put()
遇到{0, 0, 0}这种指向自己的例子就会stackoverflow
所以应该先把点put到map里面，然后再添加neighbors
71.08 %
public class Solution {
// DFS with prunning
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
//key-original node, value-copied new node
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
return cloneGraph(node, map);
}
private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
if (node == null) return null;
if (map.containsKey(node)) return map.get(node);
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node, newNode);
for (UndirectedGraphNode neighbor : node.neighbors) {
newNode.neighbors.add(cloneGraph(neighbor, map));
}
return newNode;
}
}
67.19 %
public class Solution {
private Map<UndirectedGraphNode, UndirectedGraphNode> map;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return node;
map = new HashMap<>();
return clone(node);
}
//clone the current node
//return new node
private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (map.containsKey(node)) {
return map.get(node);
}
map.put(node, new UndirectedGraphNode(node.label));
for (UndirectedGraphNode neighbor : node.neighbors) {
map.get(node).neighbors.add(clone(neighbor));
}
return map.get(node);
}
}
No comments:
Post a Comment