207. Course Schedule

harry xie
2024-09-22 15:46:23

解題程式碼

var canFinish = function (numCourses, prerequisites) {
  let queue = [];
  const graph = new Map();
  const indegrees = new Array(numCourses).fill(0);

  for (const [e, v] of prerequisites) {
    // v: 需先修的課
    if (graph.has(v)) {
      graph.get(v).push(e);
    } else {
      graph.set(v, [e]);
    }
    indegrees[e]++;
  }

  for (let i = 0; i < indegrees.length; i++) {
    if (indegrees[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const v = queue.shift();
    if (!graph.has(v)) continue;

    for (const e of graph.get(v)) {
      indegrees[e]--;
      if (indegrees[e] === 0) queue.push(e);
    }
  }

  return !indegrees.find((e) => e === 1);
};

解題思路演算法

題目中有段 You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.，就是在講節點和邊的關係，以 [1,0] 來說，就是 1 => 0，0 沒有任何修課限制

test case: prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]

不可能完成的情況為圖中出現環，例如題目給的範例 2

解題作法是可以先用一個 hashMap，key 儲存的是各課程，value 為陣列，儲存它需要先修的課並另外用一個陣列去儲存各課程所需的先修課數目

然後用 queue 記錄當前可以修的課程，每彈出一個課程，當作修完課，就將陣列中先修課有該課的課程值 -1

當 queue 清空時，若 hashMap 中還有 value > 0，就代表課沒辦法上完，結果為 false又或是可以用一個陣列去儲存已經上過的課(queue 彈出的元素)，若數目和 numCourses 不同，也代表課沒辦法上完，結果為 false

LeetCode 官方題解說明得很詳細，推薦參考，附在參考資料連結

解法的時間空間複雜度

時間複雜度: O(E + V)
空間複雜度: O(E + V)

參考資料

207. Course Schedule 课程表 LeetCode 力扣官方题解

图文详解面试常考算法 拓扑排序

拓撲順序是指一張有向圖經過拓撲排序後，每一個點的先後順序一張圖有許多種拓撲順序只要不違背圖上每一條邊的先後規定，要怎麼排列圖上的點都行