【LeetCode】210. 课程表 II——拓扑排序

这篇具有很好参考价值的文章主要介绍了【LeetCode】210. 课程表 II——拓扑排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:210. 课程表 II

题目描述:
现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。

例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
``
【LeetCode】210. 课程表 II——拓扑排序,Go,LeetCode,leetcode,算法,拓扑排序,golang
数据范围:
【LeetCode】210. 课程表 II——拓扑排序,Go,LeetCode,leetcode,算法,拓扑排序,golang

题解:从题目描述来看,很容易就知道是拓扑排序问题了,问题在于如何存图,如何解答,存图方式比较多,邻接表、邻接矩阵,解方面:遍历、搜索、以及队列都能完成该题的解答,实现方面很多时候还是会依赖一些语言特性,比如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 = j
				break
			}
		}
		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(n+m)文章来源地址https://www.toymoban.com/news/detail-706121.html

到了这里,关于【LeetCode】210. 课程表 II——拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-09-10 LeetCode每日一题(课程表 II)

    点击跳转到题目位置 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。 返回你为了学完所

    2024年02月09日
    浏览(49)
  • java实现课程表 II

    题目: 现在你总共有  numCourses  门课需要选,记为  0  到  numCourses - 1 。给你一个数组  prerequisites  ,其中  prerequisites[i] = [ai, bi]  ,表示在选修课程  ai  前  必须  先选修  bi  。 例如,想要学习课程  0  ,你需要先完成课程  1  ,我们用一个匹配来表示: [0,1]  。

    2024年02月09日
    浏览(45)
  • 想要精通算法和SQL的成长之路 - 课程表II

    想要精通算法和SQL的成长之路 - 系列导航 原题链接 核心知识: 拓扑排序是专门 应用于有向图的算法。 BFS 的写法就叫拓扑排序,核心就是: 让入度为0的节点入队。 拓扑排序的 结果不唯一。 同时拓扑排序有一个重要的功能: 能够检测有向图中是否存在环。 我们先分析一下

    2024年02月09日
    浏览(35)
  • leetcode207. 课程表

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先

    2023年04月24日
    浏览(44)
  • leetcode 630. 课程表 III

    这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返回你最多可以修读的课

    2024年02月16日
    浏览(43)
  • 【图论】Leetcode 207. 课程表【中等】

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先

    2024年04月14日
    浏览(47)
  • LeetCode 0630.课程表 III:贪心 + 优先队列

    力扣题目链接:https://leetcode.cn/problems/course-schedule-iii/ 这里有 n 门不同的在线课程,按从 1 到 n  编号。给你一个数组 courses ,其中 courses[i] = [duration i , lastDay i ] 表示第 i 门课将会 持续 上 duration i 天课,并且必须在不晚于 lastDay i 的时候完成。 你的学期从第 1 天开始。且不能

    2024年02月09日
    浏览(37)
  • 2023-09-09 LeetCode每日一题(课程表)

    点击跳转到题目位置 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学

    2024年02月09日
    浏览(53)
  • 2023-09-11 LeetCode每日一题(课程表 III)

    点击跳转到题目位置 这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返

    2024年02月09日
    浏览(40)
  • 【LeetCode热题100】打卡第38天:课程表&实现前缀树

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月17日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包