题目描述
现在你总共有 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]
作答思路
通过这道题用来做有向图的遍历复习
首先构建图元素的数据结构应该是一个map,其中key是表示各个顶点的整数,value是一个数组,代表每个顶点的出边,因此每个顶点为起点有多少条边,这个map的value数组就有多少个元素
构建图的代码
本题需要选取从root节点出发,并且入度从小到大的顺序,如果没有入度为0的点,直接返回-1
代码示例
-1、首先进行有向图的构建,初始化一个课程编号0~n-1的map,其中map的key是自身的整型下标,value为了去除重复的元素,使用HashSet。注意,起始的课程应该在二元组的右边,因此应该使用course[x][1]的值作为map的key;此外,为了统计先后顺序,需要记录每个顶点的入度(顶点作为终点的边的数量)。
int []inDegrees = new int[courseNum];
public void constructGraph(int [][]course) {
for(int i=0; i< course.length; i++) {
map.put(i,new HashSet<>());
}
//根据起点终点构建课程表的边
for(int i=0; i< course.length; i++) {
map.get(course[i][1]).add(course[i][1]);
inDegrees[course[i][0]]++;
}
}
- 构建完图之后,选择入队列的节点
for(int i= 0; i< numCourses; i++) {
if(inDegrees[i] == 0) {
queue.offer(i);
}
}
- 出队列,做入度递减的判断,并继续选择未访问过的入度为0的入队列,还要注意不能让入度为0的顶点是反复入队列的重复顶点,因此需要对其做去重处理,使用一个bool类型的数组记录访问过的顶点。
while(!queue.isEmpty()) {
int top = queue.poll();
result[index++] = top;
visited[top] = true;
count++;
Set<Integer> valueSet = orderGraph.get(top);
if(valueSet != null) {
for(Integer ele:valueSet) {
inDegrees[ele] --;
if(inDegrees[ele] == 0 && !visited[ele]) {
queue.offer(ele);
}
}
}
}
最终,result的数组内的元素记录了应该学习的课程表顺序,如果这个数组的元素数量等于所有给出的课程数,说明我们找到了一组解。否则返回int [0]
题目总结
做图的类型题的时候,我们主要解决图的数据结构和遍历这两个问题,第一个问题:我们应该使用数组加HashSet的结构存储;对于遍历,我们应该采用DFS或者BFS的方式,其中DFS的表现形式主要为递归;BFS则是使用队列层次遍历。