【每日一题】LeetCode 207. 课程表 TypeScript

你这个学期必须选修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 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i]中的所有课程对互不相同function canFinish(numCourses: number, prerequisites: number[][]): boolean { //BFS //1.建一个邻接表记录每门课学完后能解锁哪些课 const graph:number[][] Array.from({length:numCourses},()[]) //2.记录每门课还有多少先修课没学入度 const indegree:number[] new Array(numCourses).fill(0) //3.填表和入度 for(const [a,b] of prerequisites){ //先修b指向a即b学完后才能学a graph[b].push(a) //a多了一个先修要求 indegree[a] } //4.找出所有入度为0的课没有先修要求入队 const queue:number[] [] for(let i0;inumCourses;i){ if(indegree[i]0) queue.push(i) } // 5.开始剥洋葱 let learned 0 //已经学了多少门 while(queue.length0){ const course queue.shift()! //取出一门可以学的课 learned //遍历这门课能解锁的所有后续课 for(const next of graph[course]){ indegree[next]-- //后续课的一个先修课已经完成了 if(indegree[next]0){ //如果后续课的左右先修都完成了它也可以学了 queue.push(next) } } } return learnednumCourses };共勉