我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 210. 課程表 II
題目
現在你總共有 n 門課需要選，記為 0 到 n-1，
在選修某些課程之前需要一些先修課程， 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，回傳你為了學完所有課程所安排的學習順序，
可能會有多個正確的順序，你只要回傳一種就可以了，如果不可能完成所有課程，回傳一個空陣列，
示例 1:
輸入: 2, [[1,0]]
輸出: [0,1]
解釋: 總共有 2 門課程，要學習課程 1，你需要先完成課程 0，因此，正確的課程順序為 [0,1] ，
示例 2:
輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程，要學習課程 3，你應該先完成課程 1 和課程 2，并且課程 1 和課程 2 都應該排在課程 0 之后，
因此，一個正確的課程順序是 [0,1,2,3] ，另一個正確的排序是 [0,2,1,3] ，
說明:
- 輸入的先決條件是由邊緣串列表示的圖形，而不是鄰接矩陣，詳情請參見圖的表示法，
- 你可以假定輸入的先決條件中沒有重復的邊，
提示:
- 這個問題相當于查找一個回圈是否存在于有向圖中，如果存在回圈，則不存在拓撲排序，因此不可能選取所有課程進行學習，
- 通過 DFS 進行拓撲排序 - 一個關于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念，
- 拓撲排序也可以通過 BFS 完成，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/course-schedule-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
拓撲排序經典題
本題的解法有：
- BFS
- DFS
- Kahn
暫只寫了BFS解法；
思路1-BFS/廣度優先
思路決議：課程的依賴關系最后畫成是一張有向圖，箭頭指向是被依賴課程，一個指向就是一個度；
對于本題，統計節點的入度，0入度的就是BFS的起點，每處理完一批0入度的點，0入度指向的點入度-1，新的0入度點將變為下一次BFS的起點，如此回圈處理即可；
處理的最終結果有兩種：
- 有向圖中存在環，即存在有要學A課程必須先學B課程，但是要學B課程又必須先學A課程，形成“死鎖”，即不可能實作學完所有課程；
- 有向圖中無環，可以學完所有課程；
步驟：
- 建立陣列統計點的入度，統計記錄依賴當前節點的其他節點；
- 找出所有0入度的點，這些課程是沒有前置依賴的必須先學的課程；
- 開始BFS，找所有依賴0入度的節點，順序記錄到結果陣列result，將依賴當前0入度的其他點的入度-1，遇到減為0入度的加入BFS佇列，待下一次BFS處理；
- 校驗result陣列的實際長度，若不等于總課程數，說明出現了環無法學完所有課程，否則可學完所有課程；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
演算法原始碼示例
package leetcode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @author ZhouJie
* @date 2020年5月17日 下午9:31:14
* @Description: 210. 課程表 II
*
*/
public class LeetCode_0210 {
}
class Solution_210 {
/**
* @author: ZhouJie
* @date: 2020年5月17日 下午9:31:33
* @param: @param numCourses
* @param: @param prerequisites
* @param: @return
* @return: int[]
* @Description: 1-拓撲排序，BFS解法；
*
*/
public int[] findOrder_1(int numCourses, int[][] prerequisites) {
int[] input = new int[numCourses];
int[] result = new int[numCourses];
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
// 統計節點的入度和依賴關系
for (int[] arr : prerequisites) {
input[arr[0]]++;
if (!map.containsKey(arr[1])) {
map.put(arr[1], new ArrayList<Integer>());
}
map.get(arr[1]).add(arr[0]);
}
Queue<Integer> queue = new LinkedList<Integer>();
// 0度的節點入佇列，即首個必須課程
for (int i = 0; i < numCourses; i++) {
if (input[i] == 0) {
queue.offer(i);
}
}
int k = 0;
while (!queue.isEmpty()) {
int p = queue.poll();
// 課程選修記錄
result[k++] = p;
// 若當前課程是前置課程，則減少其對應后置課程的入度，若入度減少為0則入隊
if (map.containsKey(p)) {
for (Integer val : map.get(p)) {
input[val]--;
if (input[val] == 0) {
queue.offer(val);
}
}
}
}
return k == numCourses ? result : new int[] {};
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185229.html
標籤：Java
上一篇：mixin很難嗎？