国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Course Schedule 課程計(jì)劃

Amio / 2775人閱讀

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 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?


For example:


2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.


2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.


Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
拓?fù)渑判?/b> 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

先修課問題本質(zhì)上是一個(gè)有向圖，如果這個(gè)圖無環(huán)，我們可以根據(jù)拓?fù)渑判虮闅v到所有節(jié)點(diǎn)，如果有環(huán)則拓?fù)渑判驘o法完成，遍歷到的節(jié)點(diǎn)將少于總節(jié)點(diǎn)數(shù)，因?yàn)橛械墓?jié)點(diǎn)是孤島。這題我們先根據(jù)邊的關(guān)系，建一個(gè)圖，并計(jì)算每個(gè)節(jié)點(diǎn)的入度，這里用的是數(shù)組來建圖。然后從入度為0的節(jié)點(diǎn)，也就是入口開始廣度優(yōu)先搜索，按照拓?fù)渑判虻捻樞虮闅v，最后看遍歷過的節(jié)點(diǎn)數(shù)和總節(jié)點(diǎn)數(shù)的關(guān)系就行了。拓?fù)渑判虻氖褂梅椒▍⒁娡馕淖值洹?/p> 代碼 

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        // 先初始化圖，每個(gè)賦一個(gè)空列表
        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList();
        }
        // 根據(jù)邊建立圖，并計(jì)算入度
        for(int i = 0; i < prerequisites.length; i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        // 找到有向圖的入口
        Queue queue = new LinkedList();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }
        // 按照拓?fù)渑判虻捻樞颍M(jìn)行廣度優(yōu)先搜索
        int cnt = 0;
        while(!queue.isEmpty()){
            Integer curr = queue.poll();
            cnt++;
            ArrayList nexts = graph[curr];
            for(int i = 0; i < nexts.size(); i++){
                int next = nexts.get(i);
                indegree[next]--;
                if(indegree[next] == 0){
                    queue.offer(next); 
                }
            }
        }
        return cnt == numCourses;
    }
}

2018/10

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make(map[int][]int)
    indegree := make([]int, numCourses)
    // build the graph, count the indegree for each course
    for _, prerequisite := range prerequisites {
        course1 := prerequisite[0]
        course2 := prerequisite[1]
        if graph[course2] != nil {
            graph[course2] = append(graph[course2], course1)
        } else {
            graph[course2] = []int{course1}
        }
        indegree[course1]++
    }
    // find out those with 0 indegree as roots of the graph
    var queue []int
    for i, degree := range indegree {
        if degree == 0 {
            queue = append(queue, i)
        }
    }
    // traverse the graph from each root, decrement the indegree for each leaf
    count := 0
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        count++
        for _, course := range graph[curr] {
            indegree[course]--
            // once a node"s indegree is 0, it becomes a root too
            if indegree[course] == 0 {
                queue = append(queue, course)
            }
        }
    }
    // if all nodes have been the root before, we traversed the entire graph
    return count == numCourses
}
Course Schedule II 
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.


For example:


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].
拓?fù)渑判?/b> 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

和I不同的是，這題要返回路徑。其實(shí)也沒有什么不同的，不過是多加一個(gè)數(shù)組，記錄廣度優(yōu)先搜索的遍歷順序就行了。

注意

當(dāng)沒有先修課的時(shí)候，隨便返回一個(gè)順序就行了，所以初始化的時(shí)候就初始化為升序序列，方便后面直接返回。

代碼 
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){
            if(graph[prerequisites[i][1]] == null){
                graph[prerequisites[i][1]] = new ArrayList();
            }
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        Queue queue = new LinkedList();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }
        // 用idx記錄輸出數(shù)組的下標(biāo)
        int idx = 0;
        while(!queue.isEmpty()){
            Integer curr = queue.poll();
            res[idx++] = curr;
            if(graph[curr] == null) continue;
            for(Integer next : graph[curr]){
                if(--indegree[next] == 0){
                    queue.offer(next); 
                }
            }
        }
        // 如果有環(huán)則返回空數(shù)組
        return idx != numCourses ? new int[0] : res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/64634.html

相關(guān)文章

  • 210. Course Schedule II

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

    lbool 評論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 評論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 評論0 收藏0

  • [LeetCode] 207. 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, which is expressed ...

    ephererid 評論0 收藏0

  • 207. Course Schedule

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

    Nino 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<