课程表-LeetCode100

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

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

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/course-schedule/submissions/567458574/?envType=study-plan-v2&envId=top-100-liked

如果把数据展开，我们会得到一张这样的图。

我们可以发现：1.加入我们学习了0课程，1课程就可以学了，1->2,学完后，但是你发现有3和4两门课，但是学完2不可以学4，因为学4之前你得学3，所以，你只能2->3,3->4,4->5,至此你才能学完所有得课程；

2.你发现如果一个点，它没有前缀点，我们就可以直接使用，并可以删除掉与相连得边，并较少相关点得点缀点的个数；

3.如果前缀点的都不为0，说明可能绕城一个环了，则不可能成功；

4.整体的解决流程：

① 构造执行点和前缀表的数据结构；

②判断前缀点为0的所有点，并将其存储起来tmp；

③在tmp中找到可以进行学习的点，遍历对应的指向点，根据数值修改前缀点的表，如果前缀点中的数据为0，则加入到map中；如果数据为0，则记录进行学习过的课程数count；

④根据记录的课程数count和总课程数判断，如果一致，则全部读完，否则，失败；

相关代码：

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> tmp =new ArrayList<>();//给每个课程创建一个可指向的链表for(int i=0;i<numCourses;i++){List<Integer> cur =new ArrayList<>();tmp.add(cur);}//创建前缀点表int [] in =new int [numCourses];//填值for(int [] cur1 :prerequisites){int a =cur1[0];int b =cur1[1];in[b]++;List<Integer> cur2 =tmp.get(a);cur2.add(b);}int ret =0;Queue<Integer> queue =new LinkedList<>();//判断有无入读为0的点，将其存储起来for(int i=0;i<numCourses;i++){if(in[i]==0){//找getqueue.add(i);}}//进行学习while(queue.size()>0){int t =queue.poll();//学习List<Integer> cur2 =tmp.get(t);for(int val:cur2 ){  //遍历，修改前缀表in[val]--;if(in[val]==0){   //学习过了queue.add(val);}}cur2=null;  //将其置空，写不写都行，为了理解ret++;  //记录学习过的课程数}if(ret!=numCourses){  //判断是否都学习过return false;}return true;}
}