题目要求
你这个学期必须选修 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 。这是不可能的。
解题思路
这道题是一道典型的拓扑排序的题。
拓扑排序是图论中的理论,主要流程如下:
- 首先构造邻接表和入度
- 遍历入度为0的节点,同时将依赖他们的节点入度-1
- 再次遍历此时入度为0的节点,重复步骤2
- 直到没有入度为0的节点
几个特点:
- 拓扑排序只能处理有向无环图
- 如果有环,则无法遍历完所有节点
Java代码
class Solution {
// 构造一个数据结构,记录所有的邻接节点
class Course{
int id;
Set<Course> children;
int in;
public Course(int id){
this.id = id;
this.children = new HashSet<>();
}
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
Course[] courses = new Course[numCourses];
for(int i = 0; i < numCourses; i++){
courses[i] = new Course(i);
}›
for(int i = 0; i < prerequisites.length; i++){
int[] require = prerequisites[i];
courses[require[0]].children.add(courses[require[1]]);
courses[require[1]].in++;
}
// 通过队列来遍历
Queue<Course> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
// 将入度为0的节点加入队列
if(courses[i].in == 0) queue.offer(courses[i]);
}
int size = 0;
while(!queue.isEmpty()){
Course course = queue.poll();
size++;
// 修改当前节点所有的邻接节点的入度
for(Course child : course.children){
child.in--;
// 如果邻接节点入度为0,加入队列
if(child.in == 0){
queue.offer(child);
}
}
}
// 如果遍历完所有的节点,则表示无环
return size == numCourses && queue.isEmpty();
}
}
总结
Grind75里面的题目,通常都是挑选每一类里面最典型的题目,基本上一眼就能看出需要用什么算法。
拓扑排序是一种非常常见的算法,有一套规范的写法,必须掌握。
网友评论