Skip to main content

2-28 210.课程表 II

Date：2022-03-06 20:01:10

题目：210.课程表 II(😕)​

图、拓扑排序、BFS(广度优先搜索)

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例​

示例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]

说明​

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

前提知识​

图、拓扑排序、DFS、BFS（深度、广度优先搜索）

分析​

此题虽然根据他人代码，我也做出来了，但过程还是没理解。由于本身对图认识不够，后续还要加强练习

题解​

function main() {
  const numCourses = 4
  const prerequisites = [
    [1, 0],
    [2, 0],
    [3, 1],
    [3, 2],
  ]

  console.log('[]:', findOrder(numCourses, prerequisites))
}

main()

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  let res = []

  // 计算入度和关系
  // 这里的关系是 依赖课程: [课程1，课程2]，也就是指课程1和2依赖于依赖课程
  const inDeeps = new Array(numCourses).fill(0)
  const relationship: {
    [key: number]: number[]
  } = {}
  for (let i = 0; i < prerequisites.length; ++i) {
    const value = prerequisites[i][0]
    const dep = prerequisites[i][1]

    inDeeps[value]++

    if (relationship[dep]) {
      relationship[dep].push(value)
    } else {
      relationship[dep] = [value]
    }
  }

  // 生成队列
  const queue = []
  for (let i = 0; i < inDeeps.length; ++i) {
    // 只需要入度为0的，因为这是开始条件，注意queue中放的是课程编号
    if (inDeeps[i] == 0) queue.push(i)
  }

  console.log('[queue]:', queue)
  // 开始广度优先搜索
  while (queue.length) {
    const dep = queue.shift()
    res.push(dep)

    // 后续的课程
    const courses = relationship[dep]
    for (let i = 0; courses && i < courses.length; ++i) {
      const course = courses[i]

      // 向后推进
      const depAfter = --inDeeps[course]
      if (depAfter == 0) {
        queue.push(course)
      }
    }
  }

  // 结果的数量，一定与总课程数一致
  return res.length == numCourses ? res : []
}

这是根据代码，分析的一次各个变量的状态

4, [[1,0],[2,0],[3,1],[3,2]]

inDeep:
[
  0,1,1,2
]

queue:
[
  0
]

relationship:
[
  '0': [1, 2],
  '1': [3],
  '2': [3]
]

扩展1：图、拓扑序列​

图基础知识

入度：指向改点的边数

207-1.png

扩展2：贪心算法​

贪心算法简而言之：每一步最优，则全局最优。