210. Course Schedule II

lbool 发布于2019-08-16 10:36 / 659人阅读

摘要：建立入度组成，把原来输入的无规律，转换成另一种表示图的方法。找到为零的点，放到里，也就是我们图的入口。对于它的也就是指向的。如果这些的入度也变成，也就变成了新的入口，加入到里，重复返回结果。这里题目有可能没有预修课，可以直接上任意课程。

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云服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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