目錄
207. 課程表
題目描述：
實(shí)現(xiàn)代碼與解析：
拓?fù)渑判?/p>
210. 課程表 II
題目描述：
實(shí)現(xiàn)代碼與解析：
拓?fù)渑判?/p>
原理思路：
207. 課程表
題目描述：
????????你這個(gè)學(xué)期必須選修?numCourses?門課程，記為?0?到?numCourses - 1?。
在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組?prerequisites?給出，其中?prerequisites[i] = [ai, bi]?，表示如果要學(xué)習(xí)課程?ai?則?必須?先學(xué)習(xí)課程??bi?。
- 例如，先修課程對(duì)?
[0, 1]?表示：想要學(xué)習(xí)課程?0?，你需要先完成課程?1?。
請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回?true?；否則，返回?false?。????????
示例 1：
輸入：numCourses = 2, prerequisites = [[1,0]] 輸出：true 解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。
示例 2：
輸入：numCourses = 2, prerequisites = [[1,0],[0,1]] 輸出：false 解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成?課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCourses-
prerequisites[i]?中的所有課程對(duì)?互不相同
實(shí)現(xiàn)代碼與解析：
拓?fù)渑判?/strong>
class Solution {
public:
vector<int> h = vector<int>(2010, -1), e = vector<int>(20010, 0), ne = vector<int>(20010, 0), d = vector<int>(2010, 0);
int idx = 0, cnt = 0;
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
// 拓?fù)渑判? bool topsort(int n)
{
queue<int> q; // 隊(duì)列
for (int i = 0; i < n; i++)
if (d[i] == 0) q.push(i); // 入度為 0的入隊(duì)
while(q.size())
{
int t = q.front();
cnt++;
q.pop();
// bfs
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
d[j]--; // 此節(jié)點(diǎn)入度減一
if(d[j] == 0) q.push(j); // 若入度減為0，入隊(duì)
}
}
if (cnt < n) return 0; // 入隊(duì)的結(jié)點(diǎn)小于總結(jié)點(diǎn)數(shù)
else return 1;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
for (int i = 0; i < prerequisites.size(); i++)
{
add(prerequisites[i][0], prerequisites[i][1]);
d[prerequisites[i][1]]++; // 入度++
}
if (topsort(numCourses) == 0) return false;
else return true;
}
};210. 課程表 II
題目描述：
????????現(xiàn)在你總共有?numCourses?門課需要選，記為?0?到?numCourses - 1。給你一個(gè)數(shù)組?prerequisites?，其中?prerequisites[i] = [ai, bi]?，表示在選修課程?ai?前?必須?先選修?bi?。
- 例如，想要學(xué)習(xí)課程?
0?，你需要先完成課程?1?，我們用一個(gè)匹配來表示：[0,1]?。
返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序?？赡軙?huì)有多個(gè)正確的順序，你只要返回?任意一種?就可以了。如果不可能完成所有課程，返回?一個(gè)空數(shù)組?。
示例 1：
輸入：numCourses = 2, prerequisites = [[1,0]] 輸出：[0,1] 解釋：總共有 2 門課程。要學(xué)習(xí)課程 1，你需要先完成課程 0。因此，正確的課程順序?yàn)?[0,1] 。
示例 2：
輸入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 輸出：[0,2,1,3] 解釋：總共有 4 門課程。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后。 因此，一個(gè)正確的課程順序是?[0,1,2,3] 。另一個(gè)正確的排序是?[0,2,1,3]。
示例 3：
輸入：numCourses = 1, prerequisites = [] 輸出：[0]
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi- 所有
[ai, bi]?互不相同
實(shí)現(xiàn)代碼與解析：
拓?fù)渑判?/strong>
class Solution {
public:
vector<int> h = vector<int>(2010, -1), e = vector<int>(20010, 0), ne = vector<int>(20010, 0), d = vector<int>(2010, 0), top = vector<int>(2010, 0);
int idx = 0, cnt = 0;
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
// 拓?fù)渑判? bool topsort(int n)
{
queue<int> q; // 隊(duì)列
for (int i = 0; i < n; i++)
if (d[i] == 0) q.push(i); // 入度為 0的入隊(duì)
while(q.size())
{
int t = q.front();
top[cnt++] = t;
q.pop();
// bfs
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
d[j]--; // 此節(jié)點(diǎn)入度減一
if(d[j] == 0) q.push(j); // 若入度減為0，入隊(duì)
}
}
if (cnt < n) return 0; // 入隊(duì)的結(jié)點(diǎn)小于總結(jié)點(diǎn)數(shù)
else return 1;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
for (int i = 0; i < prerequisites.size(); i++)
{
add(prerequisites[i][1], prerequisites[i][0]);
d[prerequisites[i][0]]++; // 入度++
}
if (topsort(numCourses) == 0) return {};
else return vector<int>(top.begin(), top.begin() + numCourses);
}
};原理思路：
? ? ? ? 其實(shí)兩道題基本上差不多，就是一個(gè)需要返回順序，一個(gè)不用返回。
? ? ? ? 本質(zhì)上都是拓?fù)渑判虻幕具\(yùn)用，一點(diǎn)都不用改的。
拓?fù)渑判蛟斀猓◣в蠧++模板）_Cosmoshhhyyy的博客-CSDN博客文章來源：http://www.zghlxwxcb.cn/news/detail-708011.html
? ? ? ? 不懂的可以看我之前寫的拓?fù)渑判蚪馕觥?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-708011.html
到了這里，關(guān)于LeetCode：207. 課程表、210. 課程表 II（拓?fù)渑判?C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
