leetcode 207.课程表

发表于 | 分类于
写了又忘，菜的很真实

207. 课程表

用时 1h 30min

我哭了， 一道常见 mid 写了 一个多小时

还是一道以前写过两遍的题

哈哈哈哈哈哈哈哈哈 也太真实了

拿到题 就开始写 DFS，然后写着写着 不知道为什么 把 DFS 和 BFS 混在一起用了，也不知道自己是怎么想的

导致做出来的结果全部是 TRUE

最后只好看了一眼自己以前怎么写出来的才过

BFS 的解法

思路就是 先遍历一遍数组，存储 每个课程有几个依赖 ， 和 被依赖的课程 map 表

然后找到依赖是 0 的课程，进行 BFS，每次出栈都视为学习了一门课程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var canFinish = function (numCourses, prerequisites) {
  let cources = new Array(numCourses).fill(0);
  if (!prerequisites.length) return true;
  let requireMap = {};
  for (let i = 0; i < prerequisites.length; i++) {
    const [cource, reqCource] = prerequisites[i];
    cources[cource]++;
    if (!requireMap[reqCource]) {
      requireMap[reqCource] = [cource];
    } else {
      requireMap[reqCource].push(cource);
    }
  }
  let stack = [];
  let count = 0;
  for (let i = 0; i < cources.length; i++) {
    if (cources[i] === 0) {
      stack.push(i);
    }
  }
  while (stack.length) {
    let cur = stack.pop();
    count++;
    let canLearn = requireMap[cur];
    if (canLearn && canLearn.length) {
      for (let i = 0; i < canLearn.length; i++) {
        cources[canLearn[i]]--;
        if (cources[canLearn[i]] === 0) {
          stack.push(canLearn[i]);
        }
      }
    }
  }

  return count === numCourses;
};

DFS 解法

考察从每个课程出发做 DFS 是否存在环

在每项 DFS 中，每个课程初始值是 0 ， 访问过的课程赋值 1 ， 一次 DFS 完成后 赋值 -1

遇到 -1 说明该课程出发不存在环，返回 true ，如果是 1 说明在一次 DFS 中存在环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var canFinish = function (numCourses, prerequisites) {
  let cources = new Array(numCourses).fill(0);
  if (!prerequisites.length) return true;
  let requireMap = {};
  for (let i = 0; i < prerequisites.length; i++) {
    const [cource, reqCource] = prerequisites[i];
    if (!requireMap[reqCource]) {
      requireMap[reqCource] = [cource];
    } else {
      requireMap[reqCource].push(cource);
    }
  }
  var walk = function (id) {
    if (cources[id] === 1) return false;
    if (cources[id] === -1) return true;
    cources[id] = 1;
    let arr = requireMap[id];
    if (arr) {
      for (let i = 0; i < arr.length; i++) {
        if (!walk(arr[i])) return false;
      }
    }
    cources[id] = -1;
    return true;
  };
  for (let i = 0; i < cources.length; i++) {
    if (!walk(i)) return false;
  }
  return true;
};