【LeetCode】【算法】209. 课程表

LeetCode 209. 课程表

题目描述

你这个学期必须选修numCourses门课程，记为0到numCourses- 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出，其中 prerequisites[i] = [a_i,b_i] ，表示如果要学习课程a_i则必须先学习课程b_i。
例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

思路

这是一个经典的拓扑排序问题，什么是拓扑排序问题？我理解就是需要判断先完成什么事儿再完成什么事儿的那种问题
可以考虑通过建立一个图，对于入度为0的图先开始做搜索，看最后能不能把所有的图节点遍历掉。
第一步：根据给定的prerequisites建立一个类型为List<List<Integer>>edges的列表，其中下标i表示第i门课程，List<Integer>则表示第i门课程的后置课程；同时还有一个indeg=new int[numCourses]数组，该数组中记录每门课程有多少门前置课程
第二步：建立队列，遍历indeg数组，寻找那些前置课程门数为0的课程，并入队到队列尾
第三步：建立一个visited变量存储学习的课程数量，while(队列不为空时)

• ①出队首元素;
• ②学习课程数+1；
• ③通过上面的第一步的List<List<Integer>> edges获得该门课程的所有后置课程，遍历里边的元素for (int v:edges.get(u))对于里面的元素执行：
  --indeg[v];因为该门课程的前置课程数量-1
  if (indeg[v]==0)说明该元素此时入度为0（没有前置课程了），入队到队列尾

第四步：返回visited == numCourses，就知道能否学完所有课程了

代码

class Solution {
    List<List<Integer>> edges;
    int[] indeg;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 建立图以后做搜索
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++){
            edges.add(new ArrayList<>());
        }
        indeg = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
            ++indeg[prerequisite[0]]; // 记录这个位置有几个子节点，便于后续做广度优先搜索 -> 但是真的有必要吗？edges[prerequisite[0]]的长度不行吗
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0){ // 找到入度为0的节点开始广度优先搜索
                queue.offer(i);
            }
        }

        int visited = 0;
        while (!queue.isEmpty()){
            ++visited;
            int u = queue.poll(); // 出队
            for (int v: edges.get(u)){ // 广度优先搜索，里面的内容入队
                --indeg[v];
                if (indeg[v] == 0){ // 直到这个节点不再被其他节点所指，才能入队继续遍历它下面的节点
                    queue.offer(v);
                }
            }
        }

        return visited == numCourses;
    }
}