☆打卡算法☆LeetCode 210. 课程表 II 算法解析
☆打卡算法☆LeetCode 210. 课程表 II 算法解析
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个课程数numCourses，还有选修科目prerequisites表示学习选修a1前需要先选修b1，返回为了完成课程所安排的学习顺序。”
题目链接：
来源：力扣（LeetCode）
链接： 210. 课程表 II - 力扣（LeetCode）
2、题目描述
现在你总共有 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] 。二、解题
1、思路分析
这道题跟207题.课程表类似，207题是判断是否可以学习完所有的课程，而本题是要返回选课的顺序。
207题使用了深度优先搜索算法，这道题也可以使用深度优先搜索算法DFS。
本题是一道经典的拓扑排序问题，拓扑排序对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
在拓扑排序过程中，如果某个节点的长度为0，说明这个课程的先修课已经学完了，下一门课就可以学习这一门，将这门课添加到答案中即可。
2、代码实现
代码参考：
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
3、时间复杂度
时间复杂度：O(n+m)
其中n是课程数，m是先修课程的要求数，这其实就是对图进行深度优先搜索的时间复杂度。
空间复杂度：O(n+m)
题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，需要存储成领接表的形式，因此空间复杂度为O(n+m)。
三、总结
拓扑排序是专门用用于有向图的算法：
这道题使用深度优先搜索算法DFS，根据拓扑排序思路。
用数组模拟领接表。
用数组模拟队列。
让当前入度为0的节点入队。