Блог

Я работаю над литкодом 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. В чем может быть проблема в приведенном выше коде?

Это происходит потому, что вы изменяете входной график, делая:

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