Clone Graph LeetCode 133

Question

我在做Leetcode 133。克隆图:

给定在连接的中的节点的引用无向图。

返回深拷贝(克隆)图形

图中的每个节点包含一个值(int)和它的邻居列表(List[Node])。

class Node {
public int val;
public List<Node> neighbors;
}

测试用例格式:为简单起见，每个节点的值与节点的索引(1-索引)相同。例如，第一个节点为val == 1，第二个节点为val == 2，依此类推。图在测试用例中使用邻接表表示。

我已经为此挣扎了很长时间。我的解决方案:

/**
* // Definition for a Node.
* function Node(val, neighbors) {
*    this.val = val === undefined ? 0 : val;
*    this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {
if (!node) {
return node;
}
const nodeCopy = new Node(node.val);
let stack = [node];
let nodeMap = {};
nodeMap[node.val] = nodeCopy;
while (stack.length > 0) {
const currentNode = stack.shift();
const currentNodeCopy = nodeMap[currentNode.val];
let nodeNeighbors = currentNode.neighbors;
while (nodeNeighbors.length > 0) {
const currentNeighbor = nodeNeighbors.shift();
let existingNeighborCopy = nodeMap[currentNeighbor.val];
// console.log(existingNeighborCopy);
if (!existingNeighborCopy) {
stack.push(currentNeighbor);
nodeMap[currentNeighbor.val] = new Node(currentNeighbor.val);
}
// console.log('Existing Neighbor');
// Already Visited;
currentNodeCopy.neighbors.push(nodeMap[currentNeighbor.val]);
}
}
console.log(nodeCopy);
console.log(nodeCopy.neighbors[0]);
return nodeMap[node.val];
};

它迭代地执行DFS。但是对于给定的基本测试用例:

[[2,4],[1,3],[2,4],[1,3]]

抛出输出:

值为2的节点在原图中不存在

这似乎是完全错误的，因为有一个节点有2个值。上述代码中的问题可能是什么?

Answer 1

发生这种情况是因为通过以下操作改变了输入图形

nodeNeighbors.shift();

显然，LeetCode测试代码没有维护自己的输入图副本，所以当它运行代码并尝试将输入图与返回的图进行比较时，它发现在输入图中节点1没有邻居，因此它说没有节点2。

所以不要改变输入图形，并更改以下两行:

while (nodeNeighbors.length > 0) {
const currentNeighbor = nodeNeighbors.shift();

…:

for (const currentNeighbor of nodeNeighbors) {

另一个实现你可以考虑使用递归，而不是使用显式堆栈。

var cloneGraph = function(node) {
if (!node) return null;
const nodeMap = [0];
const dfs = ({ val, neighbors }) =>
Object.assign(nodeMap[val] = new Node(val), {
neighbors: neighbors.map(neighbor =>
nodeMap[neighbor.val] ?? dfs(neighbor)
)
});
return dfs(node);
};

Answer 2

在java中添加一个具有更好的T, S复杂度的解决方案。

class Solution {
// O(N)time
// O(N)space
HashMap<Integer, Node> graphDataMap = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null)
return node;
depthFirstSearch(node);
return graphDataMap.get(node.val);
}
void depthFirstSearch(Node node) {
if (graphDataMap.containsKey(node.val)) {
return;
}
Node cloneNode = new Node(node.val);
graphDataMap.put(node.val, cloneNode);
for (Node n : node.neighbors) {
depthFirstSearch(n);
cloneNode.neighbors.add(graphDataMap.get(n.val));
}
}
}
```