[LeetCode/LintCode] Course Schedule II

Lavender 發布于2019-08-15 17:49 / 3038人閱讀

Problem

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

Given n = 2, prerequisites = [[1,0]]
Return [0,1]

Given n = 4, prerequisites = [1,0],[2,0],[3,1],[3,2]]
Return [0,1,2,3] or [0,2,1,3]

Solution

public class Solution {
    /*
     * @param n: a total of n courses
     * @param pre: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int n, int[][] pre) {
        // write your code here
        ArrayList[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList();
        }
        
        int[] indegree = new int[n];
        for (int i = 0; i < pre.length; i++) {
            graph[pre[i][1]].add(pre[i][0]);
            indegree[pre[i][0]]++;
        }
        
        Queue queue = new LinkedList();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.add(i);
        }
        
        int[] result = new int[n];
        int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            ArrayList list = graph[node];
            for (int i = 0; i < list.size(); i++) {
                int cur = list.get(i);
                indegree[cur]--;
                if (indegree[cur] == 0) queue.add(cur);
            }
        }
        return index == n ? result : new int[0];
    }
}

GPU云服務器云服務器 Course Schedule node-schedule Schedule定時器

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69467.html

210. Course Schedule II

摘要：建立入度組成，把原來輸入的無規律，轉換成另一種表示圖的方法。找到為零的點，放到里，也就是我們圖的入口。對于它的也就是指向的。如果這些的入度也變成，也就變成了新的入口，加入到里，重復返回結果。這里題目有可能沒有預修課，可以直接上任意課程。 Some courses may have prerequisites, for example to take course 0 you have ...

lbool 2019-08-16 10:36 評論0 收藏0
[LeetCode] 210. Course Schedule II

Problem 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...

zhkai 2019-08-19 11:12 評論0 收藏0
【LC總結】圖、拓撲排序 (Course Schedule I, II/Alien Dictiona

Course Schedule Problem 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, whi...

gaara 2019-08-14 15:54 評論0 收藏0
[Leetcode] Course Schedule 課程計劃

Course Schedule I 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 e...

Amio 2019-08-14 12:40 評論0 收藏0
[LeetCode/LintCode] Number of Islands [DFS]

摘要：兩個循環遍歷整個矩陣，出現則將其周圍相鄰的全部標記為，用子函數遞歸標記。注意里每次遞歸都要判斷邊界。寫一個的，寫熟練。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

Fourierr 2019-08-14 15:15 評論0 收藏0