乐趣区

关于java:LeetCode133克隆图

jiezi

克隆图

题目形容：给你无向 连通 图中一个节点的援用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都蕴含它的值 val（int）和其街坊的列表（list[Node]）。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：深度优先遍历

首先，如果以后节点为空，不必解决，间接返回。

否则，应用一个 Map 即 visited 来存储曾经解决过的图节点和相应的克隆节点，递归处理过程如下：

  • 判断以后节点是否在 visited 中，如果在，则阐明曾经解决过了，则间接从 visited 中取出以后节点的克隆并返回。
  • 否则，依据以后节点克隆出一个新的克隆节点，新克隆的节点的街坊节点初始化为空，而后将以后节点和新的克隆节点增加到 visited 中；
  • 而后递归解决以后节点的街坊节点。

最初，返回以后节点的克隆节点。

解法二：广度优先遍历

同样的，首先，如果以后节点为空，不必解决，间接返回。

否则，也是须要初始化一个 Map 即 visited 来存储曾经解决过的图节点和相应的克隆节点，首先将以后节点和由以后节点克隆的节点增加到 visited 中，而后将以后节点增加到一个队列 queue 中，而后解决队列中的节点，晓得队列不为空，处理过程如下：

  • 取出队列的头结点为 curNode；
  • 遍历解决 curNode 节点的街坊节点；
  • 如果以后街坊节点不在 visited，则将其和相应的克隆节点增加到 visited 中，并将其加到队列中；
  • 而后将以后街坊节点的克隆节点增加到 curNode 的克隆节点的街坊节点列表中。

最初，返回初始节点的克隆节点。

注 ：图相干的算法还是理解的不多，得多学学。

import com.kaesar.leetcode.GraphNode;

import java.util.*;

public class LeetCode_133 {private static Map<GraphNode, GraphNode> visited = new HashMap<>();

    /**
     * 深度优先遍历
     *
     * @param node 以后节点
     * @return
     */
    public static GraphNode cloneGraph(GraphNode node) {if (node == null) {return node;}
        // 如果该节点曾经被拜访过了，则间接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {return visited.get(node);
        }

        // 克隆以后节点
        GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 递归解决以后节点的街坊节点
        for (GraphNode neighbor : node.neighbors) {cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }

    /**
     * 广度优先遍历
     *
     * @param node 以后节点
     * @return
     */
    public static GraphNode cloneGraph2(GraphNode node) {if (node == null) {return node;}

        HashMap<GraphNode, GraphNode> visited = new HashMap<>();

        Queue<GraphNode> queue = new LinkedList<>();
        // 将以后节点增加到队列中
        queue.add(node);
        // 克隆第一个节点并存储到哈希表中
        visited.put(node, new GraphNode(node.val, new ArrayList<>()));

        // 广度优先遍历
        while (!queue.isEmpty()) {
            // 取出队列的头节点
            GraphNode curNode = queue.remove();
            // 遍历以后节点的街坊节点
            for (GraphNode neighbor : curNode.neighbors) {if (!visited.containsKey(neighbor)) {visited.put(neighbor, new GraphNode(neighbor.val, new ArrayList<>()));
                    // 将街坊节点增加到队列中
                    queue.add(neighbor);
                }

                // 更新以后节点的街坊节点列表
                visited.get(curNode).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }

    public static void main(String[] args) {}}

【每日寄语】 本人入手，饥寒交迫！

退出移动版