你這個學(xué)期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。

在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學(xué)習(xí)課程 ai 則 必須 先學(xué)習(xí)課程 bi 。

例如，先修課程對 [0, 1] 表示：想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 。
請你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false

https://leetcode-cn.com/problems/course-schedule/

示例1：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。

示例2：

輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的。

提示：

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有課程對 互不相同

Java解法

思路：

• 初步思考，這種有關(guān)聯(lián)的數(shù)據(jù)類似于鏈表結(jié)構(gòu)，如果鏈表有環(huán)，那么這個數(shù)據(jù)將互相死鎖無法學(xué)習(xí)

  • 雙向鏈表：前節(jié)點為前置學(xué)習(xí)課程，后節(jié)點為后續(xù)學(xué)習(xí)課程，無前節(jié)點可作為學(xué)習(xí)課程起點
  • 學(xué)習(xí)數(shù)量：可以通過起點遍歷記數(shù)返回

• 因為沒用提供數(shù)據(jù)結(jié)構(gòu)供解題，這里先采用hashmap來記錄對應(yīng)關(guān)系

  public static boolean canFinish(int numCourses, int[][] prerequisites) {
      if (prerequisites == null||prerequisites.length==0) {
          return true;
      }
      HashMap<Integer, List<Integer>> map = new HashMap<>();//記錄學(xué) a課需要先學(xué)的b課
      HashMap<Integer, List<Integer>> map2 = new HashMap<>();//記錄 已學(xué) a課，可以學(xué)的b課
      for (int[] prerequisite : prerequisites) {
          List<Integer> list = map.getOrDefault(prerequisite[0], new ArrayList<>());
          list.add(prerequisite[1]);
          List<Integer> list1 = map.getOrDefault(prerequisite[1], new ArrayList<>());
          map.put(prerequisite[0], list);
          map.put(prerequisite[1], list1);
  
          List<Integer> integers = map2.getOrDefault(prerequisite[1], new ArrayList<>());
          integers.add(prerequisite[0]);
          map2.put(prerequisite[1],integers);
      }
      List<Integer> start = new ArrayList<>();
      for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
          if (entry.getValue()==null||entry.getValue().size()==0) {
              start.add(entry.getKey());
          }
      }
      int count = numCourses;
      for (Integer integer : start) {
          count--;
          int unLearn = learnFinish(map2, integer, count);
          if (unLearn<=0) {
              return true;
          }
          count = unLearn;
      }
      return count<=0;
  }
  public static int learnFinish(HashMap<Integer, List<Integer>> map,int index,int count){
      List<Integer> integers = map.getOrDefault(index,new ArrayList<>());
      count-=integers.size();
      for (Integer i : integers) {
          count -= learnFinish(map, i, count);
      }
      return count;
  }
  

• 不知道是理解錯誤，這里的課程數(shù)無關(guān)結(jié)果，這里要求的是課程是不是能學(xué)完，腦殼大

• 參考官方解：拓?fù)渑判?深度優(yōu)先搜索+回溯

  • 使用數(shù)組記錄搜索狀態(tài)，使用棧記錄回溯完成遍歷節(jié)點

package sj.shimmer.algorithm.m4_2021;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by SJ on 2021/4/19.
 */

class D82 {
    public static void main(String[] args) {
        System.out.println(canFinish(2,new int[][]{
                {1,0},
                {2,1},
        }));
        System.out.println(canFinish(20,new int[][]{
                {0,10},
                {3,18},
                {5,5},
                {6,11},
                {11,14},
                {13,1},
                {15,1},
                {17,4},
        }));
        System.out.println(canFinish(1,new int[][]{}));
    }

    static List<List<Integer>> edges;
    static int[] visited;//0 未搜索，1 搜索中（有環(huán)，無法完成），2 完成
    static boolean valid = true;

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);//記錄學(xué)完 可以學(xué)的課，
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);//開始深度搜索
            }
        }
        return valid;
    }

    public static void dfs(int u) {
        visited[u] = 1;
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}

image

官方解

https://leetcode-cn.com/problems/course-schedule/submissions/

1. 深度優(yōu)先搜索

   如上

   • 時間復(fù)雜度： O(n+m)

• 空間復(fù)雜度： O(n+m)

2. 廣度優(yōu)先搜索：上方逆序操作