千家信息网

golang中怎么利用leetcode实现课程表排序

发表于:2026-10-31 作者:千家信息网编辑
千家信息网最后更新 2026年10月31日,这期内容当中小编将会给大家带来有关golang中怎么利用leetcode实现课程表排序,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。示例 1:输入: 2, [[1,
千家信息网最后更新 2026年10月31日golang中怎么利用leetcode实现课程表排序

这期内容当中小编将会给大家带来有关golang中怎么利用leetcode实现课程表排序,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

示例 1:

输入: 2, [[1,0]]

输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。

因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。

你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。

通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。

拓扑排序也可以通过 BFS 完成。

解题思路:

1,对课程排序是,前一篇的递进,有向图的top排序,采用广度优先搜索(BFS)

2,首先将边缘列表转化成逆邻接矩阵,并记录每个前缀课程的入度

3,入度为0 的课程没有依赖,可以先上,放入队列

4,一次从队列中取节点

A,放入返回数据

B,将依赖此节点的所有邻接节点的入度减一(删除此节点后,邻接节点的依赖减少)

C,将修正后入度为0 的节点放入队列

D,循环直至队列为空

4,返回数据如果长度等于课程长度,说明没有环,否则有环

func findOrder(numCourses int, prerequisites [][]int) []int {    inverse_adj:=make([][]int,numCourses)    out_degree:=make([]int,numCourses) //入度    for i:=0;i        //将边缘列表转换成逆邻接矩阵的形式        out_degree[prerequisites[i][0]]++        inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0])       }    r:=BFS(inverse_adj,out_degree)    if len(r)==numCourses{        return r    }    return nil}
func BFS(inverse_adj [][]int,out_degree []int)(r []int){ var q queue for i:=0;i if out_degree[i]==0{ //入度为0,可以作为终点 q.push(i) } } for !q.empty(){ top:=q.pop() r=append([]int{top},r...) for _,precursor:=range(inverse_adj[top]){ //将当前节点移除,所有前驱节点的出度减1 out_degree[precursor]-- if out_degree[precursor]==0{ q.push(precursor) } } } return r}
type queue struct{ data []int}
func(q*queue)empty()bool{ return len(q.data)==0}
func(q*queue)push(i int){ q.data=append(q.data,i)}
func(q*queue)pop()int{ r:=q.data[len(q.data)-1] q.data=q.data[:len(q.data)-1] return r}

上述就是小编为大家分享的golang中怎么利用leetcode实现课程表排序了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注行业资讯频道。

课程 排序 节点 拓扑 输入 矩阵 边缘 队列 学习 循环 课程表 先决条件 内容 数据 有向图 条件 示例 长度 顺序 分析 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 广东万易互联网科技有限公司惠州分公司 互联网科技工作委员会副主任毛军 科技互联网企业 科技赋能下的互联网金融 今日互联网科技 科技互联网技术 互联网科技公司发展 凡科互联网科技 友谊互联网络科技 上游互联网科技 深圳期待互联网科技 北京三清互联网科技 受益于互联网科技的高速发展 阿大互联网科技有限公司 深圳市优智互联网科技有限公司 健康食品互联网创新科技园项目 互联网保险科技创业 科技赋能视角下互联网保险发展 广州千川互联网科技有限公司 互联网风格科技公司名称 南京欣网互联网络科技 港股互联网科技股 广州互联网络科技有限公司 菲比寻常互联网科技 卫星互联网科技股票 天速互联网络科技有限公司 恒银科技与互联网金融 重庆威客帮互联网科技 广州新华互联网科技学校电竞方面 北京瑞云互联网科技有限公司
0