2023-09-09每日一題
一、題目編號
207. 課程表
二、題目鏈接
點擊跳轉(zhuǎn)到題目位置
三、題目描述
你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。
- 例如，先修課程對 [0, 1] 表示：想要學習課程 0 ，你需要先完成課程 1 。
請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。
示例 1：
示例 2：
提示：文章來源：http://www.zghlxwxcb.cn/news/detail-703825.html
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- prerequisites[i] 中的所有課程對 互不相同
四、解題代碼
class Solution {
#define maxn 100010
vector<int> edges[maxn];
int deg[maxn];
void addEdge(int v, int u){
edges[u].push_back(v);
++deg[v];
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int i;
int n=prerequisites.size();
queue<int> q;
int hash[maxn];
memset(hash,0,sizeof(hash));
for(i=0;i<numCourses;i++){
edges[i].clear();
deg[i] = 0;
hash[i] = 0;
}
for(int i=0;i<n;i++){
addEdge(prerequisites[i][1],prerequisites[i][0]);
}
int x=numCourses;
for(int i=0;i<numCourses;i++){
if(!deg[i]){
q.push(i);
x--;
hash[i]=1;
}
}
while( !q.empty() ){
int u=q.front();
q.pop();
for(int i=0;i<edges[u].size();i++){
int v=edges[u][i];
deg[v]--;
if(hash[v]==0 && deg[v]==0){
q.push(v);
hash[v]=1;
x--;
}
}
}
if(x==0){
return true;
}
return false;
}
};
五、解題思路
(1) 使用拓撲排序可以很輕松的的解決這道題目。這也是拓撲排序的一道經(jīng)典例題。文章來源地址http://www.zghlxwxcb.cn/news/detail-703825.html
到了這里，關(guān)于2023-09-09 LeetCode每日一題(課程表)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
