LeetCode207. Course Schedule

1、题目链接

https://leetcode.com/problems/course-schedule/

2、解题思路

这道题的意思是说有一共有N门课程，然后在你修这些课程的时候会有一定的限制，比如在你修课程1的时候必须先修课程0，把这样一组关系我们用[1, 0]来表示，然后给你一个二维数组表示这些课程的关系，问你是否有可能修完所有的课程，我们先来看一下示例：

示例1：

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例2：

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

示例2中为什么不能修完呢，因为这里存在一个死环，修完课程1必须先修课程0，然后修完课程0又必须修完课程1，那么问题就好办了，我们只要能找到这个里面是否存在类似的死环就好了，一开始我想错了，以为这是无向图找环，后面才发现是有向图，题目提示用拓扑排序的思想来做，于是就有了如下的代码，定义了一个入度的数组，然后将数组中的所有课程的入度先计算一遍，然后我们找到入度为0的课程，然后将其子节点的入度进行减1，最后在遍历这个入度数组，如果还存在入度不为0的课程，那么就认为这个里面就一定有环；这个过程就相当于把入度为0的点及其边都删掉，到最后看还有没有额外的删不掉的点，我们想象一下，如果一个点它和另外一个点或几个点形成环（有向图的环），那么这些点的入度肯定都不为0，所以我们需要排除那些形成不了环的点。

3、代码

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (null == prerequisites) {
        return false;
    }
    int len = prerequisites.length;
    if (len == 0) {
        return true;
    }
    boolean[] visited = new boolean[numCourses];  //用来标记某一门课程是否已经被遍历过
    int[] inDegree = new int[numCourses];  //表示图的入度的数组
    for (int[] prerequisite : prerequisites) {
        inDegree[prerequisite[0]]++;
    }
    while (true) {
        int index;
        // 找到入度是0的节点
        for (index = 0; index < numCourses; index++) {
            if (!visited[index] && inDegree[index] == 0) {
                break;
            }
        }
        if (index == numCourses) {
            break;
        }
        // 遍历每一个节点，找到与入度为0的节点的子节点，将其入度减1
        for (int[] prerequisite : prerequisites) {
            if (prerequisite[1] == index) {
                inDegree[prerequisite[0]]--;
            }
        }
        visited[index] = true;
    }
    //判断所有节点的入度都是否为0
    for (int degree : inDegree) {
        if (degree > 0) {
            return false;
        }
    }
    return true;
}

4、结果

WX20190804-142236@2x.png