赞
踩
现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。
例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
作者:liweiwei1419
链接:https://leetcode-cn.com/problems/course-schedule-ii/solution/tuo-bu-pai-xu-shen-du-you-xian-bian-li-python-dai-/
BFS 的写法就叫「拓扑排序」
拓扑排序」的一个附加效果是:能够顺带检测有向图中是否存在环。
拓扑排序实际上应用的是贪心算法,贪心算法简而言之:每一步最优,则全局最优。
每一次都从图中删除没有前驱的顶点,这里并不需要真正的做删除操作,我们可以设置一个入度数组,每一轮都输出入度为 00 的结点,并移除它、修改它指向的结点的入度(-1−1即可),依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除,则说明“不能完成所有课程的学习”。
在代码具体实现的时候,除了保存入度为 00 的队列,我们还需要两个辅助的数据结构:
1、邻接表:通过结点的索引,我们能够得到这个结点的后继结点;
2、入度数组:通过结点的索引,我们能够得到指向这个结点的结点个数。
创建HashSet<>等集合类型的数组要给数组初始化,否则赋值的时候会报空指针异常。
class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] incnt = new int[numCourses]; Queue<Integer> que = new LinkedList<>(); HashSet<Integer>[] adjoin = new HashSet[numCourses]; for (int i = 0; i < numCourses; i++) { adjoin[i] = new HashSet<>(); } for(int[] pre : prerequisites){ adjoin[pre[1]].add(pre[0]); incnt[pre[0]]++; } for(int i = 0; i < incnt.length; i++){ if(incnt[i] == 0){ que.offer(i); } } int[] ans = new int[numCourses]; int index = 0; while(!que.isEmpty()){ int tmp = que.poll(); ans[index++] = tmp; HashSet<Integer> adj = adjoin[tmp]; for(Integer ad : adj){ if(--incnt[ad] == 0){ que.offer(ad); } } } return index == numCourses ? ans : new int[0]; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。