js.207.课程表

链接：207. 课程表 - 力扣（LeetCode）

题目：

你这个学期必须选修numCourses门课程，记为0到numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi。

• 例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。

请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

示例 1：

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

示例 2：

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

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i]中的所有课程对互不相同

思路：

用有向图描述依赖关系
示例：n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
课 0, 1, 2 没有先修课，可以直接选。其余的课，都有两门先修课。
我们用有向图来展现这种依赖关系（做事情的先后关系）：

这种叫 有向无环图，把一个 有向无环图 转成 线性的排序 就叫 拓扑排序。
有向图有 入度 和 出度 的概念：
如果存在一条有向边 A --> B，则这条边给 A 增加了 1 个出度，给 B 增加了 1 个入度。
所以，顶点 0、1、2 的入度为 0。顶点 3、4、5 的入度为 2。
每次只能选你能上的课
每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。
假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。
接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。
接着选 2，导致课 4 的入度变 0。
现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。

入度数组：课号 0 到 n - 1 作为索引，通过遍历先决条件表求出对应的初始入度。
邻接表：用哈希表记录依赖关系（也可以用二维矩阵，但有点大）
key：课号
value：依赖这门课的后续课（数组）

参考思路链接：https://leetcode.cn/problems/course-schedule/solutions/250377/bao-mu-shi-ti-jie-shou-ba-shou-da-tong-tuo-bu-pai-/

代码：

/** * @param {number} numCourses * @param {number[][]} prerequisites * @return {boolean} */ var canFinish = function(numCourses, prerequisites) { let prelen = prerequisites.length, list = [], count = 0; let goMap = new Map(), nextMap = new Map(); for(let i = 0; i <prelen; i++) { if(goMap.has(prerequisites[i][0])) { goMap.set(prerequisites[i][0], goMap.get(prerequisites[i][0]) + 1); } else { goMap.set(prerequisites[i][0], 1); } if(nextMap.has(prerequisites[i][1])) { nextMap.get(prerequisites[i][1]).push(prerequisites[i][0]); } else { nextMap.set(prerequisites[i][1], [prerequisites[i][0]]); } } for(let i = 0; i < numCourses; i++) { if(!goMap.has(i)) { list.push(i); } } while(true) { if(list.length === 0) break; count++; let cur = list.shift(); let nextList = nextMap.get(cur) || []; for(let i = 0; i < nextList.length; i++) { if(goMap.has(nextList[i])) { let goCount = goMap.get(nextList[i]) - 1; goMap.set(nextList[i], goCount); if(goCount === 0) { list.push(nextList[i]); } } } } if(count === numCourses) { return true; } return false; };