难度:Medium
题目:
你这个学期必须选修
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 。这是不可能的。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i]
中的所有课程对 互不相同
Related Topics
- 深度优先搜索
- 广度优先搜索
- 图
- 拓扑排序
重点!!!解题思路
第一步:
明确解题手段:仔细读题,可发现要先完成前置课程,必须先完成后置课程,那么后置课程其实可以看做是前置课程的一个入度(indegree),只有当一个节点入度为0时,它才可以被学习,理解到这里就可以发现此题可使用拓扑排序来解决。
第二步:
拓扑排序思路:1.把原数组关系看作是一个图
2.需要一个能记录每个节点的入度的数组
3.需要一个二维集合来记录每个0入度节点对应的子节点
4.需要一个队列来将入度为0的节点添加到队列中去,每次出队的时候找到它们对应的子节点,并将子节点的入度-1,当子节点的入度为0就添加到队列中,继续判断
5.最后当出队数量与原数量一致,那么即为正确答案
源码+讲解:
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indeg=new int[numCourses]; //这个数组:入度统计List<List<Integer>> g=new ArrayList<>(); //二维集合: 统计每个入度为0节点对应的子节点for (int i=0;i<numCourses;i++){ //首先初始化二维集合g.add(new ArrayList<>());}Queue<Integer> q=new ArrayDeque<>(); //创建一个队列用于计数操作for (int[] prerequisite : prerequisites) {indeg[prerequisite[0]]++; //遍历给定二维数组,前置节点入度+1g.get(prerequisite[1]).add(prerequisite[0]); //后置节点对应一个前置节点}for (int i=0;i<indeg.length;i++){ //将入度为0的节点添加到队列中去if (indeg[i]==0) q.offer(i);}while (!q.isEmpty()){ int pre = q.poll(); //每次弹出的都是一个入度为0的前置节点numCourses--; //每弹出一个,相当于总节点数少一个,当numCourses为0时,才是答案for (Integer cur : g.get(pre)) { //根据前置节点取出所有后置节点,并将每个后置节点入度-1,直到减为0if (--indeg[cur]==0) q.offer(cur);}}return numCourses==0;}
}
运行结果:
如果您还有什么疑问或解答有问题,可在下方评论,我会及时回复。
系列持续更新中,点个订阅吧,喜欢练习算法那就点个攒吧