免费的软件网站,wordpress捐,要做网络推广,深圳住房和建设局网站轮候大厅想要精通算法和SQL的成长之路 - 课程表 前言一. 课程表II #xff08;拓扑排序#xff09;1.1 拓扑排序1.2 题解 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 课程表II #xff08;拓扑排序#xff09;
原题链接
1.1 拓扑排序
核心知识#xff1a;
拓扑排序是专… 想要精通算法和SQL的成长之路 - 课程表 前言一. 课程表II 拓扑排序1.1 拓扑排序1.2 题解 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 课程表II 拓扑排序
原题链接
1.1 拓扑排序
核心知识
拓扑排序是专门应用于有向图的算法。BFS的写法就叫拓扑排序核心就是让入度为0的节点入队。拓扑排序的结果不唯一。同时拓扑排序有一个重要的功能能够检测有向图中是否存在环。
我们先分析一下本题
先说下课程课程有它自己的一个先后的依赖顺序。符合 “有向” 。想要学习某个课程它的前缀课程可能有多个。那么我们可以用 “度” 的概念去标识衡量。这里是入度。
先用图来解释下本次算法的核心方向摘自leetcode题解 说白了就是
不断地找入度为0的节点然后剔除。剔除的同时维护后续节点的入度数。以此类推。
1.2 题解
那么本题我们该如何解我们一步步来我们以numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]] 为例来说。官方解释
总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
public int[] findOrder(int numCourses, int[][] prerequisites) {}那么我们可以知道这个二维数组prerequisites中第二个数字代表”前缀“第一个数字代表”后缀“。[1,0] 用图表示就是0-1。同时我们还可以计算出此时1这个节点的入度应该1。因为0指向了1。
1.首先我们要对入参做一个校验
// 1. 先判断数组或者numCourses为空的情况
if (numCourses 0) {return new int[0];
}2.我们需要遍历二维数组prerequisites中拿到所有节点的入度以及这个拓扑图的结构。
我们用inDegree[]数组表示各个节点的入度。用一个HashSet数组表示邻接表的结果。数组的索引代表的是节点的值。数组值即HashMap代表这个节点的所有后继节点。以0为例它的后继节点有1和2。
// 2. 用inDegree[] 数组表示每个节点的入度数。
// 同时维护拓扑图的结构例如0-10-2
HashSetInteger[] adj new HashSet[numCourses];
// 初始化下
for (int i 0; i numCourses; i) {adj[i] new HashSet();
}
// 构建入度
int[] inDegree new int[numCourses];
for (int[] p : prerequisites) {// 入度1inDegree[p[0]];// 把当前节点的后继节点存储起来adj[p[1]].add(p[0]);
}3.我们用一个队列用来存储入度为0的节点。
// 3.准备个队列,存储入度为0的节点
LinkedListInteger queue new LinkedList();
for (int i 0; i numCourses; i) {if (inDegree[i] 0) {queue.offer(i);}
}为啥要这一个步骤如果发现没有入度为0的节点说明啥成环了那本题就无解。如图 4.如果存在入度为0的节点我们开始往后递归做2.1节的内容。
先拿到入度为0的节点删除它把他放入结果集。同时维护后继节点的入度。如果后继节点入度数-1后为0。那么同样放入到队列中递归。
// 结果集
int[] res new int[numCourses];
// 统计结果集中的个数
int count 0;
while (!queue.isEmpty()) {// 入度为0的节点我们弹出Integer head queue.poll();// 放入结果集res[count] head;// 当前入度为0节点对应的后继节点。如果是0 -- 1,2HashSetInteger nextNodeList adj[head];// 更新后继节点的入度for (Integer nextNode : nextNodeList) {// 对应的后继节点的入度要减1inDegree[nextNode]--;// 如果入度-1后为0了。再入队if (inDegree[nextNode] 0) {queue.offer(nextNode);}}
}最后我们只需要关心结果集个数是否和题干中的numCourses一致。一致的话返回我们构建的结果集否则本题为空解
// 如果遍历完了发现count数量和 numCourses一致说明有一个正确的结果集
if (count numCourses) {return res;
}
return new int[0];最终完整代码如下
public class Test210 {public int[] findOrder(int numCourses, int[][] prerequisites) {// 1. 先判断数组或者numCourses为空的情况if (numCourses 0) {return new int[0];}// 2. 用inDegree[] 数组表示每个节点的入度数。// 同时维护拓扑图的结构例如0-10-2HashSetInteger[] adj new HashSet[numCourses];// 初始化下for (int i 0; i numCourses; i) {adj[i] new HashSet();}// 构建入度int[] inDegree new int[numCourses];for (int[] p : prerequisites) {// 入度1inDegree[p[0]];// 把当前节点的后继节点存储起来adj[p[1]].add(p[0]);}// 3.准备个队列,存储入度为0的节点LinkedListInteger queue new LinkedList();for (int i 0; i numCourses; i) {if (inDegree[i] 0) {queue.offer(i);}}// 结果集int[] res new int[numCourses];// 统计结果集中的个数int count 0;while (!queue.isEmpty()) {// 入度为0的节点我们弹出Integer head queue.poll();// 放入结果集res[count] head;// 当前入度为0节点对应的后继节点。如果是0 -- 1,2HashSetInteger nextNodeList adj[head];// 更新后继节点的入度for (Integer nextNode : nextNodeList) {// 对应的next节点的入度要减1inDegree[nextNode]--;// 如果入度-1后为0了。再入队if (inDegree[nextNode] 0) {queue.offer(nextNode);}}}// 如果遍历完了发现count数量和 numCourses一致说明有一个正确的结果集if (count numCourses) {return res;}return new int[0];}
}这个题目算是课程表系列的第二道了。第一道207. 课程表做法和上面一模一样只不过返回数组的地方返回true/false即可。
