C++實現LeetCode(207.課程清單)
[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:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
Hints:
- 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.
- 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?
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.
這道課程清單的問題對于我們學生來說應該不陌生,因為在選課的時候經常會遇到想選某一門課程,發(fā)現選它之前必須先上了哪些課程,這道題給了很多提示,第一條就告訴了這道題的本質就是在有向圖中檢測環(huán)。 LeetCode 中關于圖的題很少,有向圖的僅此一道,還有一道關于無向圖的題是 Clone Graph。個人認為圖這種數據結構相比于樹啊,鏈表啊什么的要更為復雜一些,尤其是有向圖,很麻煩。第二條提示是在講如何來表示一個有向圖,可以用邊來表示,邊是由兩個端點組成的,用兩個點來表示邊。第三第四條提示揭示了此題有兩種解法,DFS 和 BFS 都可以解此題。先來看 BFS 的解法,定義二維數組 graph 來表示這個有向圖,一維數組 in 來表示每個頂點的入度。開始先根據輸入來建立這個有向圖,并將入度數組也初始化好。然后定義一個 queue 變量,將所有入度為0的點放入隊列中,然后開始遍歷隊列,從 graph 里遍歷其連接的點,每到達一個新節(jié)點,將其入度減一,如果此時該點入度為0,則放入隊列末尾。直到遍歷完隊列中所有的值,若此時還有節(jié)點的入度不為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 的解法,也需要建立有向圖,還是用二維數組來建立,和 BFS 不同的是,像現在需要一個一維數組 visit 來記錄訪問狀態(tài),這里有三種狀態(tài),0表示還未訪問過,1表示已經訪問了,-1 表示有沖突。大體思路是,先建立好有向圖,然后從第一個門課開始,找其可構成哪門課,暫時將當前課程標記為已訪問,然后對新得到的課程調用 DFS 遞歸,直到出現新的課程已經訪問過了,則返回 false,沒有沖突的話返回 true,然后把標記為已訪問的課程改為未訪問。代碼如下:
解法二:
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
到此這篇關于C++實現LeetCode(207.課程清單)的文章就介紹到這了,更多相關C++實現課程清單內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
優(yōu)先隊列(priority_queue)的C語言實現代碼
本文簡要介紹一種基于數組二叉堆實現的優(yōu)先隊列,定義的數據結構和實現的函數接口說明如下2013-10-10