LeetCode210-课程表II

最近浙大的夸夸群挺火的

所以各大夸夸群也都春笋而出

昨天也加了两个群试试水

发现气氛也都挺nice的

其实仔细想想：这个群设立的目的还是挺好的

因为每个人都是需要赞美和鼓励的

可能是真心的，可能是虚伪的

但听者总会很开心

而我们国人不善于表达自己的赞美

所以导致很多人的烦恼

这个群设立的目的

就是想让给个正当的理由

让你去赞美别人，而别人又不会觉得很突兀

---

210-课程表II

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例1：

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

示例2：

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

思路：

这一题和第207题-课程表没什么区别，方法都是用DFS拓扑排序。对第207题-课程表不熟悉的读者可以先看看这道题。

https://blog.csdn.net/weixin_36431280/article/details/88581891

本题的话，我也举个例子，参数就和上篇文章给的参数一样，方便大家对比。

很简单，图一看就懂了。

代码如下：

import collections


class Solution(object):
    # 本题采用拓扑排序（DFS）方法，与第207题无很大差别
    # 无非就是逆序依次收集入度为0的节点
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        # 需要定义两个字典；
        # 一个字典用来记录图中每个节点的后续节点
        # 一个字典用来记录当前节点的入度数
        next_node = collections.defaultdict(list)
        rudu_num = collections.defaultdict(int)
        for node in prerequisites:
            next_node[node[0]].append(node[1])
            rudu_num[node[1]] += 1
        start = 0
        course = []
        
        while start < numCourses:
            # 如果当前节点入度为0，则将该节点的后续节点的入度数分别1
            if rudu_num[start] == 0:
                for node in next_node[start]:
                    rudu_num[node] -= 1              
                rudu_num[start] = -1
                course.append(start)
                start = 0
                continue
            if len(course) == numCourses:
                course.reverse()
                return course
            start += 1
        return []


if __name__ == "__main__":
    numCourses = 3
    prerequisites = [[0,2],[1,2],[2,0]]
    is_finish = Solution().findOrder(numCourses, prerequisites)
    print(is_finish)

不过执行效率也是挺低的，在10%左右。