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;}
}