宁晋网站建设公司,祥云县住房和城乡建设局网站,吉安微信网站,做黄金理财的网站题目链接#xff1a;210. 课程表 II 题目描述#xff1a; 现在你总共有 numCourses 门课需要选#xff0c;记为 0 到 numCourses - 1。给你一个数组 prerequisites #xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示在选修课程 ai 前 必须 先选修 bi 。
例如…题目链接210. 课程表 II 题目描述 现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。
例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。 数据范围
题解从题目描述来看很容易就知道是拓扑排序问题了问题在于如何存图如何解答存图方式比较多邻接表、邻接矩阵解方面遍历、搜索、以及队列都能完成该题的解答实现方面很多时候还是会依赖一些语言特性比如java、c中有队列可以将度为0的点放进队列中每次出队一个去边而在golang中数据结构支持相对匮乏因此可以采用遍历或者搜索方式完成。
本次采用遍历方式首先记录每个节点的入度以及边的关系遍历节点每次选出一个度为0且未被选过的节点然后去掉与这个节点相连的边一共会执行numCourses次操作当操作完后发现记录的答案中没有numCourses个节点那么表示不能完成拓扑排序动作。
直接遍历
func findOrder(numCourses int, prerequisites [][]int) []int {edges : make([][]int, numCourses, numCourses) // 存储边的关系for i : range edges {edges[i] make([]int, numCourses, numCourses)}in : make([]int, numCourses, numCourses) // 记录入度for i : 0; i len(prerequisites); i {a : prerequisites[i][0]b : prerequisites[i][1]edges[b][a] 1 // 表示a指向b的边in[a]}res : make([]int, 0, numCourses)// 遍历入度为0的点然后去掉这些点相连的边for i : 0; i numCourses; i { //共numCourses次操作k : 0 // 记录当前寻找的入度为0的点for j : 0; j numCourses; j { // 找一个度为0且未被遍历过的点if in[j] 0 {res append(res, j)in[j] -1 // 记得标记为-1已经找过的路径不再往下寻找k jbreak}}for j : 0; j numCourses; j {if edges[k][j] 1 {edges[k][j] -1 // 断开这条边in[j]-- //j点的入度-1}}}if len(res) ! numCourses {return []int{}}return res
}上述方式采用邻接矩阵方式来存储图并且通过遍历方式来计算答案虽然总共只操作n次但每次都需要找寻度为0的节点断开与该节点相连的边这样会有很多次无效的遍历浪费时间因此我们可以进行进一步的优化。
队列方式
func findOrder(numCourses int, prerequisites [][]int) []int {edges : make([][]int, numCourses, numCourses) // 存储边的关系for i : range edges {edges[i] make([]int, numCourses, numCourses)}in : make([]int, numCourses, numCourses) // 记录入度for i : 0; i len(prerequisites); i {a : prerequisites[i][0]b : prerequisites[i][1]edges[b][a] 1 // 表示a指向b的边in[a]}queue : make([]int, 0, numCourses)for i : 0; i numCourses; i {if in[i] 0 {queue append(queue, i)in[i] -1}}res : make([]int, 0, numCourses) // 记录答案// 模拟一下队列for len(queue) 0 {cur : queue[0]res append(res, cur)queue queue[1:] // 相当于除去这个元素// 从cur这个节点开始出发断边for i : 0; i numCourses; i {if edges[cur][i] 1 { // 如果有边则减少入度in[i]--edges[cur][i] -1 // 断开这条边// 如果没有依赖边了加入队列中if in[i] 0 {queue append(queue, i)}}}}if len(res) ! numCourses {return []int{}}return res
}当然前面的存储我们都采用了邻接矩阵方式存储找边的时候只能一个个遍历去寻找不妨换一种思路采用邻接表方式来存储优化一下代码
func findOrder(numCourses int, prerequisites [][]int) []int {edges : make([][]int, numCourses) // 存储边的关系fmt.Println(len(edges))in : make([]int, numCourses, numCourses) // 记录入度for i : 0; i len(prerequisites); i {u : prerequisites[i][0]v : prerequisites[i][1]edges[v] append(edges[v], u) // 记录v点指向的各个节点in[u]}queue : make([]int, 0, numCourses)for i : 0; i numCourses; i {if in[i] 0 {queue append(queue, i)}}res : make([]int, 0, numCourses) // 记录答案// 模拟一下队列for len(queue) 0 {cur : queue[0]res append(res, cur)queue queue[1:]// 从cur这个节点开始出发断边for _, v : range edges[cur] {in[v]--if in[v] 0 {queue append(queue, v)}}}if len(res) ! numCourses {return []int{}}return res
}这样每个节点最多入队一次也只会遍历m条边假设有n个节点那么时间复杂度为O(nm)
