Course Schedule II (M)

題目

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

題意

給出一組前置課程資訊，在選課程x前，必須已經修完x所有的前置課程，要求給出一組能夠修完所有課程的選課順序，如果找不出則回傳空陣列，

思路

典型的拓撲排序問題，要求找到給定圖的拓撲序列，如果存在環則回傳空陣列，求拓撲序列有兩種方法：postOrder以及入度法，

代碼實作

Java

postOrder

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> graph = new ArrayList<>();
        
        // 生成圖，注意圖中的邊是由前置課程指向當前課程
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            graph.get(pre).add(cur);
        }

        boolean[] visited = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                dfs(graph, i, visited, new boolean[numCourses], temp);
            }
        }

        // 當最終序列中的課程數與總課程數不相同時，說明圖中存在環
        if (temp.size() != numCourses) {
            return new int[0];
        }

        int[] ans = new int[numCourses];
        Collections.reverse(temp);
        for (int i = 0; i < numCourses; i++) {
            ans[i] = temp.get(i);
        }
        return ans;
    }

    private void dfs(List<List<Integer>> graph, int x, boolean[] visited, boolean[] inStack, List<Integer> temp) {
        visited[x] = true;
        inStack[x] = true;

        for (int next : graph.get(x)) {
            // 若下一個將要遍歷的課程還在遞回堆疊中，說明存在環
            if (inStack[next]) {
                return;
            }
            if (!visited[next]) {
                dfs(graph, next, visited, inStack, temp);
            }
        }

        temp.add(x);
        inStack[x] = false;
    }
}

入度法

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        Deque<Integer> q = new ArrayDeque<>();

        // 生成圖，注意圖中的邊是由前置課程指向當前課程
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            graph.get(pre).add(cur);
            inDegree[cur]++;
        }

        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y : graph.get(x)) {
                inDegree[y]--;
                if (inDegree[y] == 0) {
                    q.offer(y);
                }
            }
            temp.add(x);
        }

        // 當最終序列中的課程數與總課程數不相同時，說明圖中存在環
        if (temp.size() != numCourses) {
            return new int[0];
        }

        int[] ans = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            ans[i] = temp.get(i);
        }
        return ans;
    }
}

JavaScript

postOrder

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  let ans = []
  let visited = []
  let edges = new Map(new Array(numCourses).fill(0).map((v, index) => [index, []]))
  for (let edge of prerequisites) {
    if (!edges.has(edge[1])) {
      edges.set(edge[1], [])
    }
    edges.get(edge[1]).push(edge[0])
  }

  for (let i = 0; i < numCourses; i++) {
    if (!visited[i]) {
      dfs(i, edges, visited, [], ans)
    }
  }

  return ans.length === numCourses ? ans.reverse() : []
}

let dfs = function (u, edges, visited, instack, ans) {
  visited[u] = true
  instack[u] = true
  for (let v of edges.get(u)) {
    if (instack[v]) {
      return
    }
    if (!visited[v]) {
      dfs(v, edges, visited, instack, ans)
    }
  }
  ans.push(u)
  instack[u] = false
}

入度法

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  let ans = []
  let inDegree = new Array(numCourses).fill(0)
  let edges = new Map(new Array(numCourses).fill(0).map((v, index) => [index, []]))
  let q = []
  for (let edge of prerequisites) {
    inDegree[edge[0]]++
    edges.get(edge[1]).push(edge[0])
  }
  for (let i = 0; i < numCourses; i++) {
    if (!inDegree[i]) {
      q.push(i)
    }
  }
  while (q.length) {
    let u = q.shift()
    for (let v of edges.get(u)) {
      inDegree[v]--
      if (!inDegree[v]) {
        q.push(v)
      }
    }
    ans.push(u)
  }
  return ans.length === numCourses ? ans : []
}

標籤：其他

上一篇：回圈佇列的實作及細節

下一篇：陣列中重復的數字