ARTS：Algorithm、Review、Tip、Share

• Algorithm 算法题
• Review 英文文章
• Tip 回想一下本周工作中学到的一个小技巧
• Share思考一个技术观点、社会热点、一个产品或是一个困惑

Algorithm

本周学习图相关的算法，其实算法并不是很复杂，只是图这种数据结构表示起来比较复杂，题目给出的图的表达也并不统一，比如有时碰到邻接表，有时碰到邻接矩阵的表达方式。其实，我们不必在每种表达方式上去练所有的题目，只要掌握了在一种图的表达方式下，练习完相关的算法，碰到其他表达形式，直接转换成这种熟悉的方式，再去处理、解决就好。

一种通用、好用的图结构的表达方式（多个类文件放在一起了）：用类 Graph、Node、Edge 分别表示表示图整体结构、图中的节点、图中的边。

public class Graph {
    public Map<Integer, Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }
}

public class Node {

    public int value;
    // 入度
    public int in;
    // 出度
    public int out;
    // 与当前节点相邻的节点
    public ArrayList<Node> nexts;
    // 从当前节点出去的边
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.nexts = new ArrayList<>();
        this.edges = new ArrayList<>();
    }
}

public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

先看一道比较简单的图相关的题目

997. 找到小镇的法官

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例 1：

输入：n = 2, trust = [[1,2]]
输出：2

示例 2：

输入：n = 3, trust = [[1,3],[2,3]]
输出：3

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

提示：

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• trust 中的所有trust[i] = [ai, bi] 互不相同
• ai != bi
• 1 <= ai, bi <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-town-judge

解法描述

同题目思考得知：若给定数组中存在法官，则只能存在一人，且如果把给定数组trust看作一个图结构，元素之间的新人关系看作图中的边。则小镇法官对应的节点，其入度为 n-1、出度为 0 ，根据这个条件，就可以判定是否存在小镇法官。

注：因为此题比较简单，并没有使用上面我们定义的图表示方法。

编码实现

public int findJudge(int n, int[][] trust) {
	// 定义两个数组，分别表示对应的数组下标图中节点的入度、出度，遍历数组统计入度出度值。
    int[] in = new int[n + 1];
    int[] out = new int[n + 1];
    for (int[] edge : trust) {
        int from = edge[0];
        int to = edge[1];
        in[to] = in[to] + 1;
        out[from] = out[from] + 1;
    }

    for (int i = 1; i <= n; i++) {
        if (in[i] == n-1 && out[i] == 0) {
            return i;
        }
    }
    return -1;
}

210. 课程表 II（同：207. 课程表）

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2
都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]

提示： 1 <= numCourses <= 2000 0 <= prerequisites.length <= numCourses *
(numCourses - 1) prerequisites[i].length == 2 0 <= ai, bi < numCourses
ai != bi 所有[ai, bi] 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule-ii

解法描述

该题目实际是考察的对图的拓扑排序：首先收集入度为 0 的节点，然后去掉以该节点出发的边，再收集另外入度为 0 的节点，以此类推，遍历整个图结构，常用于项目之间有依赖关系的管理。

下面的代码实现中，先将给定的数组方式表示的图结构转换为我们熟悉的表示方法，然后再依次处理入度为 0 的节点。

编码实现

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        Graph graph = this.createGraph(prerequisites, numCourses);
        Queue<Node> zeroQueue = new LinkedList<>();

        for (Node node : graph.nodes.values()) {
            if (node.in == 0) {
                zeroQueue.offer(node);
            }
        }

        List<Integer> topologySortList = new ArrayList<>();
        while (!zeroQueue.isEmpty()) {
            Node poll = zeroQueue.poll();
            topologySortList.add(poll.value);

            for (Edge edge : poll.edges) {
                poll.out--;
                edge.to.in--;
                if (edge.to.in == 0) {
                    zeroQueue.offer(edge.to);
                }
            }
        }
        return topologySortList.size() == numCourses ? topologySortList.stream().mapToInt(Integer::intValue).toArray() : new int[]{};
    }

    public Graph createGraph(int[][] matrix, int numCourses) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            // 拿到每一条边， matrix[i]
            int from = matrix[i][1];
            int to = matrix[i][0];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!graph.nodes.containsKey(i)) {
                graph.nodes.put(i, new Node(i));
            }
        }
        return graph;
    }
}



class Graph {
    public Map<Integer, Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }


}

class Edge {
    public Node from;
    public Node to;

    public Edge(Node from, Node to) {
        this.from = from;
        this.to = to;
    }
}

class Node {

    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.nexts = new ArrayList<>();
        this.edges = new ArrayList<>();
    }
}

Review

CollectionHelpersExplained ：Guava提供的对于扩展集合框架方面的工作类的介绍

Tip

入职新公司 4 个月以来，对部门相关的业务、项目、开发流程、规范等逐渐熟悉，相信每个公司都有很多内部的规范文档，同样，我这次入职以来也看了很多目前公司的文档，但对于整体的开发流程、规范整理的日常工作类的文档却没有发现，对新入职的及其不友好、找文档也不方便。因此最近花了点时间，整理出目前工作中主要的开发流程、并链接相关联的规范文档，算作一份 日常工作手册。

趁此也发散了一下，其实对于工作中的很多情况，是需要我们即时去做好记录、做好总结的，因为人的大脑着实是“靠不住”的，它更像电脑运行的内存，而不是存储，我们可以用它来处理各种事务，但用它来记住一些事情却会频频出错。

Share

• 本周内，部门领导给我们做了一次晋升辅导相关的分享，公司对于晋升是有相关的统一标准要求的，但晋升是否成功，对于述职时的演讲也是很重要的，大部分人做的工作，还是需要很好的表达出来才能得到认可的。如何做好晋升演讲，其核心是怎样更好的展示自己、展示自己理解认知的深度、展示自己独特的价值（换做别人不行的）、给公司带来的收益等。
• 部门内每个月会组织事故复盘会，总结当月遇到的各种大大小小的事故，不限于自己部门的，我认为这种方式真的很不错，从各种遇到的问题中吸取经验教训，不至于用自己撞的头破血流的经验来提高。