克隆图LeetCode 133

Question

我在写Leetcode 133.克隆图

给出了连通的无向图中节点的引用。 返回图形的深拷贝(克隆)。 图中的每个节点都包含其邻居的值(int)和列表(List[Node])。 类节点{ public int val；公共列表邻居；} 测试用例格式： 为了简单起见，每个节点的值与节点的索引(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();

...to：

    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));
        }
    }
}