当前位置：首页 > news >正文

【每天学习一点算法 2026/05/22】课程表 II

news 2026/5/23 14:48:46

每天学习一点算法 2026/05/22

题目：课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

这题跟课程表的解法一样，只需要在回归过程往结果数组里面 push 课程即可。

functioncanFinish(numCourses:number,prerequisites:number[][]):boolean{conststatus=newArray(numCourses).fill(0)// 用于记录课程状态：0 未搜索 1 搜索中 2 已搜索constgraph:number[][]=Array.from({length:numCourses},()=>[])// 邻接表，graph[i]表示学习课程 i 需要，先学习课程集合for(const[a,b]ofprerequisites)graph[a].push(b)// 遍历 prerequisites 初始化邻接表constres=[]// 课程学习顺序// 辅助函数，用于深度优先遍历从某课程开始向上搜索它依赖课程functionhelper(course:number){if(status[course]===1)returnfalse// 如果课程处于搜索中状态返回falseif(status[course]===2)returntrue// 如果课程处于已搜索状态返回truestatus[course]=1// 修改当前课程为搜索中状态for(constpreofgraph[course]){// 递归搜索当前课程所有前置课程if(!helper(pre))returnfalse// 前置课程中有处于搜索中的会得到false, 直接返回false}// 回归到此说明此课程可以完成学习，标记为已搜索，并返回truestatus[course]=2res.push(course)// 我们递归的边界是最先需要学习的课程，所以回归时直接 push 就是学习顺序returntrue}// 主循环，遍历所有课程，进行搜索for(leti=0;i<numCourses;i++){if(status[i]===2){// 已搜索过的课程直接跳过continue}if(!helper(i)){// 当前课程建立有向图存在环，无法完成，直接返回空数组return[]}}// 遍历完成返回学习顺序数组returnres};