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

  1. Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。
  3. Review ：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。
  5. Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。
  7. 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(深度遍历)

  1. public class Solution {
  3.     // 定义一个辅助hash表，用于存储原节点和拷贝节点的映射关系
  4.     private Map<Node, Node> lookup = new HashMap<>();
  6.     public Node cloneGraph(Node node) {
  7.         // 如果node节点本身为null，直接返回null。
  8.         if (node == null) return null;
  9.         // 如果相邻节点存在于Hash表中，把相应的相邻节点取出，作为当前节点的相邻节点
  10.         if (lookup.containsKey(node)) return lookup.get(node);
  11.         // 克隆节点
  12.         Node clone = new Node(node.val, new ArrayList<>());
  13.         // 原结点和映射关系存储到hash表
  14.         lookup.put(node, clone);
  15.         // 处理相邻节点，dfs(n,lookup)进行深度优先处理，克隆后的Node加到neighbors
  16.         for (Node n : node.neighbors) clone.neighbors.add(cloneGraph(n));
  17.         // 最后返回拷贝节点
  18.         return clone;
  19.     }
  20. }

方法一：BFS(广度遍历)

  1. public class Solution {
  3.     /*
  4.      map 存储原节点和复制节点的关系
  5.      queue 存储节点
  6.      */
  7.     public Node cloneGraph(Node node) {
  8.         // 如果node节点本身为null，直接返回null。
  9.         if (node == null) return null;
  10.         // 定义HashMap用于查找复制的node
  11.         Map<Node, Node> lookup = new HashMap<>();
  12.         // 复制的node
  13.         Node clone = new Node(node.val, new ArrayList<>());
  14.         // 存储原节点和克隆节点的映射关系
  15.         lookup.put(node, clone);
  16.         Deque<Node> queue = new LinkedList<>();
  17.         queue.offer(node);
  18.         while (!queue.isEmpty()) {
  19.             Node tmp = queue.poll();
  20.             for (Node n : tmp.neighbors) {
  21.                 // map里面有从map里取出, 没有就put到map中去
  22.                 if (!lookup.containsKey(n)) {
  23.                     lookup.put(n, new Node(n.val, new ArrayList<>()));
  24.                     // node存入queue
  25.                     queue.offer(n);
  26.                 }
  27.                 // 给tmp的neighbors添加克隆节点
  28.                 lookup.get(tmp).neighbors.add(lookup.get(n));
  29.             }
  30.         }
  31.         // 返回克隆节点
  32.         return clone;
  33.     }
  34. }

Review(点评)

5个软件开发人员的不良习惯

  1. 没有代码结构和代码风格
  2. 盲目复制粘贴代码
  3. 晚上熬夜
  4. 缺乏文档
  5. 编写代码而不进行测试

Tip(技巧)

Intellij Idea 导入多个maven项目展示在右侧栏Maven Projects

Share(分享)

算法教学视频推荐