亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++實(shí)現(xiàn)LeetCode(207.課程清單)

 更新時(shí)間:2021年08月06日 16:45:14   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(207.課程清單),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 207. Course Schedule 課程清單

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 1:

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

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

Hints:

  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?
  3. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  4. Topological sort could also be done via BFS.

這道課程清單的問題對(duì)于我們學(xué)生來說應(yīng)該不陌生,因?yàn)樵谶x課的時(shí)候經(jīng)常會(huì)遇到想選某一門課程,發(fā)現(xiàn)選它之前必須先上了哪些課程,這道題給了很多提示,第一條就告訴了這道題的本質(zhì)就是在有向圖中檢測(cè)環(huán)。 LeetCode 中關(guān)于圖的題很少,有向圖的僅此一道,還有一道關(guān)于無向圖的題是 Clone Graph。個(gè)人認(rèn)為圖這種數(shù)據(jù)結(jié)構(gòu)相比于樹啊,鏈表啊什么的要更為復(fù)雜一些,尤其是有向圖,很麻煩。第二條提示是在講如何來表示一個(gè)有向圖,可以用邊來表示,邊是由兩個(gè)端點(diǎn)組成的,用兩個(gè)點(diǎn)來表示邊。第三第四條提示揭示了此題有兩種解法,DFS 和 BFS 都可以解此題。先來看 BFS 的解法,定義二維數(shù)組 graph 來表示這個(gè)有向圖,一維數(shù)組 in 來表示每個(gè)頂點(diǎn)的入度。開始先根據(jù)輸入來建立這個(gè)有向圖,并將入度數(shù)組也初始化好。然后定義一個(gè) queue 變量,將所有入度為0的點(diǎn)放入隊(duì)列中,然后開始遍歷隊(duì)列,從 graph 里遍歷其連接的點(diǎn),每到達(dá)一個(gè)新節(jié)點(diǎn),將其入度減一,如果此時(shí)該點(diǎn)入度為0,則放入隊(duì)列末尾。直到遍歷完隊(duì)列中所有的值,若此時(shí)還有節(jié)點(diǎn)的入度不為0,則說明環(huán)存在,返回 false,反之則返回 true。代碼如下:

解法一:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> in(numCourses);
        for (auto a : prerequisites) {
            graph[a[1]].push_back(a[0]);
            ++in[a[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] != 0) return false;
        }
        return true;
    }
};

下面來看 DFS 的解法,也需要建立有向圖,還是用二維數(shù)組來建立,和 BFS 不同的是,像現(xiàn)在需要一個(gè)一維數(shù)組 visit 來記錄訪問狀態(tài),這里有三種狀態(tài),0表示還未訪問過,1表示已經(jīng)訪問了,-1 表示有沖突。大體思路是,先建立好有向圖,然后從第一個(gè)門課開始,找其可構(gòu)成哪門課,暫時(shí)將當(dāng)前課程標(biāo)記為已訪問,然后對(duì)新得到的課程調(diào)用 DFS 遞歸,直到出現(xiàn)新的課程已經(jīng)訪問過了,則返回 false,沒有沖突的話返回 true,然后把標(biāo)記為已訪問的課程改為未訪問。代碼如下:

解法二:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> visit(numCourses);
        for (auto a : prerequisites) {
            graph[a[1]].push_back(a[0]);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (!canFinishDFS(graph, visit, i)) return false;
        }
        return true;
    }
    bool canFinishDFS(vector<vector<int>>& graph, vector<int>& visit, int i) {
        if (visit[i] == -1) return false;
        if (visit[i] == 1) return true;
        visit[i] = -1;
        for (auto a : graph[i]) {
            if (!canFinishDFS(graph, visit, a)) return false;
        }
        visit[i] = 1;
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/207

參考資料:

https://leetcode.com/problems/course-schedule/

https://leetcode.com/problems/course-schedule/discuss/58524/Java-DFS-and-BFS-solution

https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java

https://leetcode.com/problems/course-schedule/discuss/162743/JavaC%2B%2BPython-BFS-Topological-Sorting-O(N-%2B-E)

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(207.課程清單)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)課程清單內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • OpenCV獲取視頻的每一幀并保存為.jpg圖片

    OpenCV獲取視頻的每一幀并保存為.jpg圖片

    這篇文章主要為大家詳細(xì)介紹了OpenCV獲取視頻的每一幀,并保存為.jpg圖片,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-07-07
  • C++中priority_queue模擬實(shí)現(xiàn)的代碼示例

    C++中priority_queue模擬實(shí)現(xiàn)的代碼示例

    在c++語言中數(shù)據(jù)結(jié)構(gòu)中的堆結(jié)構(gòu)可以通過STL庫中的priority_queue 優(yōu)先隊(duì)列來實(shí)現(xiàn),這樣做極大地簡(jiǎn)化了我們的工作量,這篇文章主要給大家介紹了關(guān)于C++中priority_queue模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
    2021-08-08
  • C語言FlappyBird飛揚(yáng)的小鳥實(shí)現(xiàn)開發(fā)流程

    C語言FlappyBird飛揚(yáng)的小鳥實(shí)現(xiàn)開發(fā)流程

    因?yàn)樵诩艺撕枚嗵?,隨手玩了下自己以前做的一些小游戲,說真的,有幾個(gè)游戲做的是真的劣質(zhì),譬如 flappybird 真的讓我難以忍受,于是重做了一波分享給大家
    2022-11-11
  • 優(yōu)先隊(duì)列(priority_queue)的C語言實(shí)現(xiàn)代碼

    優(yōu)先隊(duì)列(priority_queue)的C語言實(shí)現(xiàn)代碼

    本文簡(jiǎn)要介紹一種基于數(shù)組二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列,定義的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)的函數(shù)接口說明如下
    2013-10-10
  • C語言實(shí)現(xiàn)通訊錄的示例代碼

    C語言實(shí)現(xiàn)通訊錄的示例代碼

    這篇文章主要為大家詳細(xì)介紹了如何錄音C語言實(shí)現(xiàn)一個(gè)簡(jiǎn)單的通訊錄,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-10-10
  • 亞馬遜經(jīng)典面試題實(shí)例詳解

    亞馬遜經(jīng)典面試題實(shí)例詳解

    這篇文章主要介紹了亞馬遜經(jīng)典面試題實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家,讓大家學(xué)習(xí)理解這部分內(nèi)容,需要的朋友可以參考下
    2017-10-10
  • opencv平均背景法詳解

    opencv平均背景法詳解

    這篇文章主要為大家詳細(xì)介紹了opencv平均背景法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-03-03
  • C語言借助EasyX實(shí)現(xiàn)的生命游戲源碼

    C語言借助EasyX實(shí)現(xiàn)的生命游戲源碼

    這篇文章主要介紹了C語言借助EasyX實(shí)現(xiàn)的生命游戲的方法,需要的朋友可以參考下
    2014-07-07
  • 深入了解C語言中的字符串和內(nèi)存函數(shù)

    深入了解C語言中的字符串和內(nèi)存函數(shù)

    本文主要帶大家來學(xué)習(xí)一些常用的庫函數(shù)。有了這些庫函數(shù),我們可以更加方便地操作字符串和內(nèi)存,從而提升我們的編碼效率。話不多說,我們開始吧
    2022-11-11
  • 關(guān)于C語言除0引發(fā)的思考

    關(guān)于C語言除0引發(fā)的思考

    很多 C 庫都提供了一組函數(shù)用來判斷一個(gè)浮點(diǎn)數(shù)是否是無窮大或 NaN。int _isnan(double x) 函數(shù)用來判斷一個(gè)浮點(diǎn)數(shù)是否是 NaN,而 int _finite(double x) 用以判斷一個(gè)浮點(diǎn)數(shù)是否是無窮大
    2013-08-08

最新評(píng)論