讲座嘉宾：Steve

讲座链接：请点击阅读原文
题目 1 Boarding Passes 难度 2/5
题目介绍
给定几张机票的起飞和降落城市，找到本次行程的起始城市和终点城市。
题目分析
最简单的暴力解法的话，对于N个城市，找到一个起始点，然后逐个找到路线的中间城市，直到找到所有可能的旅行路线，然后判断起始点和终止点，时间复杂度为O(N^N)，显然这样的方法是行不通的。而且，对于不同的输入，也就是从一个城市到另一个城市的机票，有可能存在起点和终点虽然固定，但是可以组成不同路线的情况（输入里没有说明机票的时间顺序），比如下图。所以说，如果是通过具体的行程路线来决定起点和终点的话，会有多种情况存在，所以可能不是一个好方法。
进一步分析，常识来看，对于某个城市，如果乘客到这里后没有离开，就说明是终点城市。但是根据题目来看，即便是终点城市，也有可能存在飞机多次飞往这个城市的情况，也就是说，从这里飞也好，飞到这里也好，最后的最后飞机都是停在了这个城市。那么对于每个城市，联想到有向图的节点出度和入度的性质，从这里起飞就是出度+1，到达这里就是入度+1，那么对于终点城市，必然有入度=出度+1，也就是到达的机票比起飞的机票多1。反过来，如果入度=出度-1，也就是到达的机票比起飞的机票少1，就说明这个城市是起始点，也就是在整个行程开始前，乘客已经来到了这个城市。而如果入度=出度，则说明这个城市是中转城市。如下图，Arrive passes (Ap)就是入度，Leave passes (Lp) 也就是出度。
那么根据这个思路，我们只需要遍历所有的机票，然后计算出每个城市的出度和入度，就能找到起点城市和终点城市，算法思路如下图，其中Count对应的其实就是Ap - Lp，如果为负值即-1，则城市为起点城市，为0则说明是中转城市，否则为1则说明是终点城市。整体的时间复杂度为O(N)。当然，这方法假设是不存在circle的情况，否则在circle的情况下，可能存在多个起点城市和终点城市，如下图。
代码实现
思路补充
其实这道题目本质上是一个有向图的问题，需要考虑图中节点（城市）出度和入度的性质。
题目 2 Sorting Photo Files 难度 1/5
题目介绍
题目分析
这道题目也不难，简单的排序问题。但是需要注意的是不可以直接按照图片的文件名来排序，因为在location之后的数字是需要按照大小来排序的，也就是beijing10要在beijing8的后面，而如果单纯按照string来对待是不够的。换个方法的话，可以用multi-keyword comparsion，就是把文件名拆分成一个location order pair，然后先按照location排序，再按照order排序即可，如下图。
复杂度的话，遍历所有的photo文件名然后构建location-order pair需要O(N)，之后排序需要O(NlogN)，所以总共的复杂度为O(NlogN)，如下图。
代码实现
题目 3 Circle Detect 难度 3/5
题目介绍
题目分析
如果是最简单的暴力解法的话，从每一个节点开始，通过DFS方法，对节点进行遍历并且标记上已经访问过的节点，之后如果遇到某个节点已经被访问过，则说明这个图中存在着circle，如下图。
复杂度的话，总共N个节点，第K个节点要访问N-K的节点，也就是一个等差数列，那么最终需要对这些节点访问O(N^2)次。这种暴力解法耗时的原因就是存在一些节点，已经在之前某次的遍历中检查过是否存在circle了，也就是有很多的重复作业，如下图。
所以如何避免重复访问节点的情况？我们其实可以只考虑从入度为0的节点开始遍历的情况，因为这些节点不存在前驱节点，也就是不存在从其他节点开始遍历到这个节点的情况，也就是这些节点不会被重复访问。如果遍历完所有入度为0的节点后，如果存在没有被访问过的节点，也就是没有一个入度为0的节点可以到达这个点，就说明图中是有circle的。但是这种方法仅仅适用于有向图，对于无向图则需要用另一种方法叫做并查集。而且存在一种特殊情况就是，如果整个的图就是一个circle的话，是无法找到入度为0的节点开始遍历的，也就在这个图中存在节点没有被访问过，如下图。
算法的实现如下图，从所有0-indegree的node开始遍历图，如果在遍历的途中发现了circle，也就是存在被访问过的节点，就说明有circle；否则，Summarize一下节点的访问情况，如果所有的0-indegree的node都尝试过，但仍然存在节点没被访问，就说明也是有circle的，否则没有。复杂度的话，所有的节点都最多被访问一次，也就是所有的edge都会被访问过一次，复杂度为O(M)，M为edge的数量。
思路补充
另外一种思路则是类似拓扑排序。如果一个有向图里面不含有circle的话，必存在节点的入度为0。那么如果我们把所有入度0的节点，以及这些节点所经过的边从图中移除，剩下的节点和边所组成的子图和原图是否有circle是等价的（因为有没有circle和入度为0的节点无关），也就是可以通过这个子图来判断原图是否有circle。根据这个想法，我们从入度为0的节点开始遍历图，在移除掉这些节点和他们的edge之后，如果有新的入度为0的节点出现，则再次以同样的方法来处理这个节点；到最后如果仍有剩余的节点没有被处理，也就是存在节点入度不为0，原图就是有circle的。算法思路和时间复杂度如下图，更多细节欢迎大家到太阁官网观看原视频。
观看原视频请复制以下链接或请点击阅读原文。
https://www.bittiger.io/classpage/RRK2eYX2WLB69ijTL
继续阅读
阅读原文