207. 课程表

难度: 中等

来源: 每日一题 2023.09.09

---

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

    }
}

分析与题解

---

• 深度优先遍历 + 环检测

  这个题目就是典型的有向图问题, 所以我们一般需要构建一个图结构, 这里使用的是 邻接表 , 不懂的可以看一下LeetCode关于图的讲解, 还是比较容易理解的. 这里就不过多叙述了.

  那么回到这个题目, 我们该如何判断这些课程是否能够完成呢? 其实我们主要的依据就是 环, 就是图中有环存在, 例如下面几种情况.

  • 两个课程相互依赖造成的环

  • 多个课程的循环依赖造成的环

  • 自己依赖自己造成的环

  

  另外, 上面是各种环的情况, 但是我们该如何通过代码判断呢? 就是我们会在遍历的过程中把先前遍历的课程节点入栈, 当遍历过程中再次遇到相同的节点, 那就是存在环了, 直接停止遍历, 返回结果即可.

  知道整体的解题方向了, 我们需要下面就说一下具体的解题过程.

  首先, 我们还是要构建有向图的邻接表的结构.

  // 创建图的邻接表
  Map<Integer, List<Integer>> cache = new HashMap<>();
  // 构建图的邻接表
  for(int[] item : prerequisites) {
      if (cache.get(item[0]) == null) {
          cache.put(item[0], new ArrayList<Integer>());
      }
      cache.get(item[0]).add(item[1]);
  }
  

  然后我们需要构建两个缓存结构 finding 和 finish, finding主要用于相当于在遍历过程中的入栈存储结构, finish主要存储已经遍历完成的结构的头节点, 当再次遇到就不需要遍历该结构了.

  Set<Integer> finish = new HashSet<Integer>();
  Set<Integer> finding = new HashSet<Integer>();
  

  然后就是遍历整个邻接表, 同时利用 finish 缓存减少遍历的次数.

  for(Integer key : cache.keySet()) {
      if (!finish.contains(key)) {
          if(dfs(key, cache, finish, finding) == false) {
              return false;
          }
      }
  }
  

  在深度优先遍历 dfs 方法中, 我们首先就是判断 当前节点是否遍历过(在 finish 数组中) 如果在查找栈中就直接停止了.

  if (finish.contains(courses)) {
      return true;
  }
  if (finding.contains(courses)) {
      return false;
  }
  

  如果上述条件都不满足, 那么就把当前的头部节点暂时放入 finding 数组中. 然后就是查找他的邻接表数组, 如果找不到环, 就把移除 finding.

  List<Integer> coursesList = cache.get(courses);
  if(coursesList != null) {
      finding.add(courses);
      for(Integer item : coursesList) {
          if(dfs(item, cache, finish, finding) == false) {
              return false;
          }
      }
      finding.remove(courses);
  }
  

  如果上面查找不到环, 那就说明当前头部节点就是一条链路, 加入到 finish 数组中, 证明遍历过. 防止重复遍历, 并且返回 True 即可.

  finish.add(courses);
  return true;
  

  接下来,我们看一下整体的解题思路如下所示.

  class Solution {
      public boolean canFinish(int numCourses, int[][] prerequisites) {
          // 创建图的邻接表
          Map<Integer, List<Integer>> cache = new HashMap<>();
          // 构建图的邻接表
          for(int[] item : prerequisites) {
              if (cache.get(item[0]) == null) {
                  cache.put(item[0], new ArrayList<Integer>());
              }
              cache.get(item[0]).add(item[1]);
          }
          // 深度优先搜索
          // 什么情况会导致不能完成, 只有一种情况就是查找到了环,如下所示
          //  A ━━━━━ B 
          //  ┃       ┃
          //  D ━━━━━ C
          // 所以我们利用深度优先遍历的方式查找环
          // 记录正在查找的课程和完成的课程
          // 查找的课程如果在查找的过程中再次出现就说明有环
          // 完成的课程数用于减少查找次数
          Set<Integer> finish = new HashSet<Integer>();
          Set<Integer> finding = new HashSet<Integer>();
          for(Integer key : cache.keySet()) {
              if (!finish.contains(key)) {
                  if(dfs(key, cache, finish, finding) == false) {
                      return false;
                  }
              }
          }
  
          return true;
      }
  
      public boolean dfs(Integer courses, Map<Integer, List<Integer>> cache, Set<Integer> finish, Set<Integer> finding) {
          if (finish.contains(courses)) {
              return true;
          }
          if (finding.contains(courses)) {
              return false;
          }
          List<Integer> coursesList = cache.get(courses);
          if(coursesList != null) {
              finding.add(courses);
              for(Integer item : coursesList) {
                  if(dfs(item, cache, finish, finding) == false) {
                      return false;
                  }
              }
              finding.remove(courses);
          }
          finish.add(courses);
          return true;
      }
  
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n), 时间复杂度与所有课程节点的个数成线性关系.
  • 空间复杂度: O(3n), 会创建三个空间 cache 、finish 以及 finding, 每一个空间都与所有课程节点数成线性关系.

  结果如下所示.