ARTS-2

2019-08-18

字数统计: 741 | 阅读时长≈ 3 分钟

ARTS是由左耳朵耗子陈皓在极客时间专栏《左耳听风》中发起的一个每周学习打卡计划。

Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。

Review ：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。

Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。

Share：分享一篇有观点和思考的技术文章。主要为了输出你的影响力，能够输出你的价值观。

Algorithm(算法)

参考文章和视频:

https://www.youtube.com/watch?v=_Zt6gwWRnHM

https://leetcode-cn.com/problems/clone-graph/solution/dfs-he-bfs-by-powcai/

https://www.youtube.com/watch?v=MOCCC_B3kNg

Leetcode 133 克隆图

这道题就是遍历整个图,所以遍历时候要记录已经访问点, 我们用一个字典记录

所以,遍历方法就有两种

思路一:DFS(深度遍历)

思路二:BFS(广度遍历)

方法一：DFS(深度遍历)

public class Solution {

    // 定义一个辅助hash表，用于存储原节点和拷贝节点的映射关系
    private Map<Node, Node> lookup = new HashMap<>();

    public Node cloneGraph(Node node) {
        // 如果node节点本身为null，直接返回null。
        if (node == null) return null;
        // 如果相邻节点存在于Hash表中，把相应的相邻节点取出，作为当前节点的相邻节点
        if (lookup.containsKey(node)) return lookup.get(node);
        // 克隆节点
        Node clone = new Node(node.val, new ArrayList<>());
        // 原结点和映射关系存储到hash表
        lookup.put(node, clone);
        // 处理相邻节点，dfs(n,lookup)进行深度优先处理，克隆后的Node加到neighbors
        for (Node n : node.neighbors) clone.neighbors.add(cloneGraph(n));
        // 最后返回拷贝节点
        return clone;
    }
}

方法一：BFS(广度遍历)

public class Solution {

    /*
     map 存储原节点和复制节点的关系
     queue 存储节点
     */
    public Node cloneGraph(Node node) {
        // 如果node节点本身为null，直接返回null。
        if (node == null) return null;
        // 定义HashMap用于查找复制的node
        Map<Node, Node> lookup = new HashMap<>();
        // 复制的node
        Node clone = new Node(node.val, new ArrayList<>());
        // 存储原节点和克隆节点的映射关系
        lookup.put(node, clone);
        Deque<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node tmp = queue.poll();
            for (Node n : tmp.neighbors) {
                // map里面有从map里取出, 没有就put到map中去
                if (!lookup.containsKey(n)) {
                    lookup.put(n, new Node(n.val, new ArrayList<>()));
                    // node存入queue
                    queue.offer(n);
                }
                // 给tmp的neighbors添加克隆节点
                lookup.get(tmp).neighbors.add(lookup.get(n));
            }
        }
        // 返回克隆节点
        return clone;
    }
}