210. Course Schedule II

lbool 發布于2019-08-16 10:36 / 681人閱讀

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

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]

2, [[1,0]] 
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]

4, [[1,0],[2,0],[3,1],[3,2]]
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].

Topo-sort 在leetcode里只有幾個題目，而且邏輯完全一樣。只要清楚的記得幾大步驟就可以解題啦。
1. 建立入度indegree.
2. 組成cousePairs，把原來輸入的無規律edges，轉換成 out -> List 另一種表示圖的方法。
3. 找到indegree為零的點，放到Queue里，也就是我們topo-sort 圖的入口。
4. 從Q里彈出點，寫到結果里。對于它的neighbors, 也就是out指向的in。這里題目意思是preCourses, 因為我們已經上過這門課，
所以需要上的課也就少了一門。如果這些neighbors的入度也變成0，也就變成了新的入口，加入到Q里，重復4.
5. 返回結果。

public class Solution {
    public int[] findOrder(int num, int[][] pres) {
        int[] res = new int[num];
        
        int[] indegree = new int[num];
        List[] pairs = new List[num];
        
        for(int[] pre : pres){
            // pre[0] in, pre[1] out
            int in = pre[0], out = pre[1];
            indegree[in]++;
            if(pairs[out] == null)
                pairs[out] = new ArrayList();
            pairs[out].add(in);
        }
        
        Queue q = new LinkedList<>();
        
        for(int i = 0; i < num; i++){
            if(indegree[i] == 0) q.offer(i);
        }
        
        int t = 0;
        while(!q.isEmpty()){
            int out = q.poll();
            res[t++] = out;
            if(pairs[out] == null) continue;      // 這里題目有可能沒有預修課，可以直接上任意課程。
            for(int in : pairs[out]){
                indegree[in]--;
                if(indegree[in] == 0) q.offer(in);
            }
        }
        
        return t == num ? res : new int[0];
    }
}

云服務器 GPU云服務器 Course rds210 Schedule rs210云服務器

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

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

[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
[LeetCode/LintCode] 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 a...

Lavender 2019-08-15 17:49 評論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
207. Course Schedule

摘要：題目解答這是一個有向圖問題，所以先建圖，然后再掃。同時記錄一共存了多少課程在里，這些課都是可以上的課。如果當兩個點在同時訪問的時候，那么構成死循環，返回。掃完所有的點都沒問題，才返回。這里總是忘記，當中時，才否則繼續循環題目：There are a total of n courses you have to take, labeled from 0 to n - 1. Some c...

Nino 2019-08-14 14:17 評論0 收藏0