首页 > 其他 > 详细

2020.8.4 力扣每日

时间:2020-08-05 00:33:13      阅读:85      评论:0      收藏:0      [点我收藏+]

技术分享图片

 1 class Solution {
 2     public boolean canFinish(int numCourses, int[][] prerequisites) {
 3         List<List<Integer>> edges = new ArrayList<List<Integer>>(); //模拟有向图
 4         int[] indegree = new int[numCourses];                       //计算入度
 5         int count = 0;                                              //计算拓扑排序元素个数
 6         for (int i = 0; i < numCourses; i++){
 7             edges.add(new ArrayList<Integer>());                    //初始化
 8         }
 9         for (int[] i : prerequisites){
10             edges.get(i[1]).add(i[0]);                              //绘制有向图
11             ++indegree[i[0]];                                       //计算入度
12         }
13         Queue<Integer> queue = new LinkedList<Integer>();           //存储0入度元素
14         for (int i = 0; i < numCourses; ++i){                       //队列初始化
15             if (indegree[i] == 0)
16                 queue.offer(i);
17         }
18         while (!queue.isEmpty()){                                  
19             int out = queue.poll();                                 //取出0入度元素
20             ++count;
21             for (int i : edges.get(out)){                           //遍历该元素的连接元素
22                 --indegree[i];                                      //连接元素入度-1
23                 if (indegree[i] == 0)                               //寻找新的0入度元素
24                     queue.offer(i);
25             }
26         }
27         return count == numCourses;                                 //判断拓扑排序元素个数是否与课程数一致
28     }
29 }

解题思路:

   根据题目中先修课程的描述,其与有向图的构造类似,而判断最终是否可以完成,则是相当于判断有向图内是否成环。这种有向图的判断是经典的拓扑排序。我们只需要根据最后拓扑排序后的结果,查看是否所有课程都在其中即可。

   先了解下什么是拓扑排序

   给定一个包含 nn 个节点的有向图 GG,我们给出它的节点编号的一种排列,如果满足:

  • 对于图 GG 中的任意一条有向边 (u, v),u 在排列中都出现在 v 的前面。

   那么称该排列是图 GG 的「拓扑排序」。

   而当一个有向图成环时,显然是违背拓扑排序的特点的,因为对于环内任意元素,我们都无法确定究竟是谁在谁之前。

   了解了拓扑排序,那么就要开始设计算法实现它。

   根据拓扑排序的特点,我们如果将所有的节点的入度计算出来,那么显然入度为0的节点,代表没有任何节点指向它,那么它一定能够出现在拓扑排序的前端。那么当我们将入度为0的节点添加入结果序列后,而当添加该节点后,我们就需要在有向图中擦去该节点,简单来说,对于这些节点来说,它们所指向的节点的入度将会-1。然后我们继续寻找入度为0的节点,直到没有入度为0的节点。

   而看到这,有没有发现有一丝的眼熟?对的,这实际上就是一种广度优先的遍历!

   所以我们可以使用广度优先遍历的模板,定义一个队列来维护入度为0的节点,出队后,计算该出队节点的后继节点的入度,若为0,则将其入队,循环操作,直到队列为空

注意点:

   由于题目要求中,下标为1的数是下标为0的数的先修课程,所以构造有向图时需反着构造,下标为1的课程在前,下标为0的课程在后

时间复杂度:O(M+N),M,N为课程数与先修课程的要求数

空间复杂度:O(M+N)

2020.8.4 力扣每日

原文:https://www.cnblogs.com/-TTY/p/13436914.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!