[LeetCode] 207. Course Schedule

ephererid 發布于2019-08-15 17:47 / 616人閱讀

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, is it possible for you to finish all courses?

Example

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

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

Solution

class Solution {
    public boolean canFinish(int num, int[][] pre) {
        //initialize graph: create list for each node(int)
        if (pre.length > num*(num-1)/2) return false;
        List[] graph = new ArrayList[num];
        for (int i = 0; i < num; i++) graph[i] = new ArrayList<>();
        
        //build graph: save children nodes to the corresponding list
        //save indegrees of children nodes to indegree[] array
        int[] indegree = new int[num];
        for (int i = 0; i < pre.length; i++) {
            indegree[pre[i][0]]++;
            graph[pre[i][1]].add(pre[i][0]);
        }
        
        //create queue to do BFS
        //save parent nodes which don"t have pre courses (indegree == 0) to the queue
        Deque queue = new ArrayDeque<>();
        for (int i = 0; i < num; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        
        //BFS: poll the parent nodes, if they have children, offer to the queue
        int count = 0;
        while (!queue.isEmpty()) {
            Integer root = queue.poll();
            count++;
            List children = graph[root];
            for (int child: children) {
                if (indegree[child] == 1) {
                    queue.offer(child);
                }
                indegree[child]--;
            }
        }
        
        return count == num;
    }
}

云服務器 GPU云服務器 Course v207 LeetCode Schedule

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

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

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
[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] 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] 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
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