描述
現(xiàn)在你總共有 n 門課需要選践叠,記為 0 到 n - 1.
一些課程在修之前需要先修另外的一些課程锌订,比如要學習課程 0 你需要先學習課程 1 ,表示為[0,1]
給定n門課以及他們的先決條件,判斷是否可能完成所有課程?
樣例
給定 n = 2怒竿,先決條件為 [[1,0]] 返回 true
給定 n = 2,先決條件為 [[1,0],[0,1]] 返回 false
代碼
public class Solution {
/**
* @param numCourses a total of n courses
* @param prerequisites a list of prerequisite pairs
* @return true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// edges用來存儲每一門課程對應的所有后續(xù)課程
// 此處新建edges的寫法要注意
List[] edges = new ArrayList[numCourses];
int[] degree = new int[numCourses];
// edges[i]本身就是一個動態(tài)數(shù)組扩氢,初始化edges
for (int i = 0;i < numCourses; i++)
edges[i] = new ArrayList<Integer>();
for (int i = 0; i < prerequisites.length; i++) {
// 題目給出的prerequisites[i][1]是先修課程耕驰,prerequisites[i][0]是后續(xù)課程
// 統(tǒng)計學習某門課需要先修的課程數(shù)目,即入度
degree[prerequisites[i][0]]++ ;
// 即把某門課的后續(xù)課程全部加入到該課對應的edges數(shù)組中
edges[prerequisites[i][1]].add(prerequisites[i][0]);
}
// degree數(shù)組中i代表的的是某一門課程
// 把度為0的課程加入隊列
Queue queue = new LinkedList();
for(int i = 0; i < degree.length; i++){
if (degree[i] == 0) {
queue.add(i);
}
}
int count = 0;
while(!queue.isEmpty()){
// 隊列里存儲的是Integer
int course = (int)queue.poll();
count ++;
// n代表當前課程的后續(xù)課程的數(shù)目
int n = edges[course].size();
// 每處理一門課程,該課程的后續(xù)課程的度都要-1
for(int i = 0; i < n; i++){
int pointer = (int)edges[course].get(i);
degree[pointer]--;
if (degree[pointer] == 0) {
queue.add(pointer);
}
}
}
// 處理的課程數(shù)目等于所有課程說明所有課程之間可以構成拓撲排序
return count == numCourses;
}
}