目录1. 课程表2.课程表 II1. 课程表你这个学期必须选修 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 。这是不可能的。思路拓扑排序深度优先搜索每个节点有三种状态未遍历遍历中遍历完。若遍历过程中遇到环则不存在拓扑排序否则存在拓扑排序。使用链表数组记录每个节点的有向边classSolution{//构图ListListIntegeredges;//记录节点状态int[]visited;//记录是否有环booleanvalidtrue;publicbooleancanFinish(intnumCourses,int[][]prerequisites){edgesnewArrayList();visitednewint[numCourses];for(inti0;inumCourses;i){edges.add(newArrayListInteger());}//构建图for(int[]info:prerequisites){edges.get(info[1]).add(info[0]);}for(inti0;inumCoursesvalid;i){if(visited[i]0){dfs(i);if(!valid){returnfalse;}}}returnvalid;}privatevoiddfs(intu){//表示正在遍历中visited[u]1;for(intv:edges.get(u)){if(visited[v]0){dfs(v);if(!valid){return;}}elseif(visited[v]1){validfalse;return;}}visited[u]2;}}时间复杂度O ( n m ) O(nm)O(nm)n nn和m mm是节点数及边数空间复杂度O ( n ) O(n)O(n)广度优先搜索与深度优先搜索逆向思维不同广度优先搜索是从入度为0的节点开始入手逐渐消除掉与入度为0的节点的边如果最后所有的节点的入度都为0则存在拓扑排序否则不存在classSolution{ListListIntegeredges;int[]inedge;publicbooleancanFinish(intnumCourses,int[][]prerequisites){edgesnewArrayList();inedgenewint[numCourses];for(inti0;inumCourses;i){edges.add(newArrayList());}for(int[]info:prerequisites){edges.get(info[1]).add(info[0]);inedge[info[0]];}QueueIntegerqueuenewLinkedList();for(inti0;inumCourses;i){if(inedge[i]0){queue.offer(i);}}intvisited0;while(!queue.isEmpty()){visited;intuqueue.poll();for(intv:edges.get(u)){inedge[v]--;if(inedge[v]0){queue.offer(v);}}}returnvisitednumCourses;}}时间复杂度O ( n m ) O(nm)O(nm)空间复杂度O ( n ) O(n)O(n)2.课程表 II现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。示例 1输入numCourses 2, prerequisites [[1,0]]输出[0,1]解释总共有 2 门课程。要学习课程 1你需要先完成课程 0。因此正确的课程顺序为 [0,1] 。示例 2输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]输出[0,2,1,3]解释总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。示例 3输入numCourses 1, prerequisites []输出[0]思路主要考虑用什么来保存遍历过的节点以及按什么顺序输出深度优先遍历中可以采用栈来保存节点因为深度遍历最先遍历完的节点是最后要上的课程最后遍历完的节点是最先要上的课因此用栈的结构最合适classSolution{ListListIntegeredges;int[]visited;booleanvalidtrue;DequeIntegerstacknewArrayDeque();publicint[]findOrder(intnumCourses,int[][]prerequisites){edgesnewArrayList();visitednewint[numCourses];for(inti0;inumCourses;i){edges.add(newArrayList());}for(int[]info:prerequisites){edges.get(info[1]).add(info[0]);}for(inti0;inumCourses;i){if(visited[i]0){dfs(i);}if(!valid){returnnewint[]{};}}int[]ansnewint[numCourses];inti0;while(!stack.isEmpty()){ans[i]stack.poll();}returnans;}privatevoiddfs(intu){visited[u]1;for(intv:edges.get(u)){if(visited[v]0){dfs(v);if(!valid){return;}}elseif(visited[v]1){validfalse;return;}}visited[u]2;stack.push(u);}}时间复杂度O ( n m ) O(nm)O(nm)n nn和m mm是节点数及边数空间复杂度O ( n ) O(n)O(n)广度优先搜索广度优先搜索是以入度为0的节点开始的因此使用队列来存储节点classSolution{ListListIntegeredges;int[]inedges;publicint[]findOrder(intnumCourses,int[][]prerequisites){edgesnewArrayList();inedgesnewint[numCourses];for(inti0;inumCourses;i){edges.add(newArrayList());}for(int[]info:prerequisites){edges.get(info[1]).add(info[0]);inedges[info[0]];}QueueIntegerqueuenewLinkedList();for(inti0;inumCourses;i){if(inedges[i]0){queue.offer(i);}}intvisited0;int[]ansnewint[numCourses];inti0;while(!queue.isEmpty()){visited;intuqueue.poll();ans[i]u;for(intv:edges.get(u)){inedges[v]--;if(inedges[v]0){queue.offer(v);}}}returnvisitednumCourses?ans:newint[]{};}}时间复杂度O ( n m ) O(nm)O(nm)n nn和m mm是节点数及边数空间复杂度O ( n ) O(n)O(n)
