网站的电子画册怎么做,网站域名备案证书下载,wordpress08影视源码,安徽建设工程信息网如何复原题目
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。 …题目
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。
示例
输入numCourses 2, prerequisites [[1,0]] 输出true 解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。
解析
这道题首先主要的思路是用bfs来写考虑有如下数据 n 6先决条件表[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]] 对于这种题要构造两个数据
每个节点的入度数量所有的节点构成一张图可以用map来表示每个节点指向了哪些节点这些节点用一个数组来表示
在此基础上不断的将入度为0的节点放到队列中消费掉消费的时候看哪些节点的入度变成了0则可以加入到队列中直到处理完成。
func canFinish(numCourses int, prerequisites [][]int) bool {var (edges make(map[int][]int, numCourses) // 边也叫邻接表存的是每个位置可以指向后面的哪些位置indeg make([]int, numCourses) // 入度数组result []int)for _, info : range prerequisites {edges[info[1]] append(edges[info[1]], info[0]) // 边中存的是每门课程构成的一个图indeg[info[0]] // 先计算出每门课程的初始入度值即在内层数组的下标0位置上出现一次就代表依赖1位置的课要先上入度就要1}queue : []int{}for i : 0; i numCourses; i {if indeg[i] 0 {queue append(queue, i) // 所有入度为0的入队列}}for len(queue) 0 {u : queue[0]queue queue[1:]result append(result, u) // 表示上了一门入度为0的课看最后课的总数是否相等for _, v : range edges[u] { // 对于入度为0的数据指向的数据进行遍历indeg[v]-- // 入度为0的数据消费了则对应的依赖的这些节点的入度就--if indeg[v] 0 {queue append(queue, v)}}}return len(result) numCourses
}
