資訊專欄INFORMATION COLUMN
摘要：建立入度組成，把原來輸入的無規(guī)律，轉(zhuǎn)換成另一種表示圖的方法。找到為零的點(diǎn)，放到里，也就是我們圖的入口。對(duì)于它的也就是指向的。如果這些的入度也變成，也就變成了新的入口，加入到里，重復(fù)返回結(jié)果。這里題目有可能沒有預(yù)修課，可以直接上任意課程。
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] 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] 4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Topo-sort 在leetcode里只有幾個(gè)題目，而且邏輯完全一樣。只要清楚的記得幾大步驟就可以解題啦。 1. 建立入度indegree. 2. 組成cousePairs，把原來輸入的無規(guī)律edges，轉(zhuǎn)換成 out -> List另一種表示圖的方法。 3. 找到indegree為零的點(diǎn)，放到Queue里，也就是我們topo-sort 圖的入口。 4. 從Q里彈出點(diǎn)，寫到結(jié)果里。對(duì)于它的neighbors, 也就是out指向的in。這里題目意思是preCourses, 因?yàn)槲覀円呀?jīng)上過這門課， 所以需要上的課也就少了一門。如果這些neighbors的入度也變成0，也就變成了新的入口，加入到Q里，重復(fù)4. 5. 返回結(jié)果。
public class Solution {
public int[] findOrder(int num, int[][] pres) {
int[] res = new int[num];
int[] indegree = new int[num];
List[] pairs = new List[num];
for(int[] pre : pres){
// pre[0] in, pre[1] out
int in = pre[0], out = pre[1];
indegree[in]++;
if(pairs[out] == null)
pairs[out] = new ArrayList();
pairs[out].add(in);
}
Queue q = new LinkedList<>();
for(int i = 0; i < num; i++){
if(indegree[i] == 0) q.offer(i);
}
int t = 0;
while(!q.isEmpty()){
int out = q.poll();
res[t++] = out;
if(pairs[out] == null) continue; // 這里題目有可能沒有預(yù)修課，可以直接上任意課程。
for(int in : pairs[out]){
indegree[in]--;
if(indegree[in] == 0) q.offer(in);
}
}
return t == num ? res : new int[0];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/70092.html
Problem 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...
Problem 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 a...
Course Schedule Problem 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, whi...
Course Schedule I 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 e...
摘要：題目解答這是一個(gè)有向圖問題，所以先建圖，然后再掃。同時(shí)記錄一共存了多少課程在里，這些課都是可以上的課。如果當(dāng)兩個(gè)點(diǎn)在同時(shí)訪問的時(shí)候，那么構(gòu)成死循環(huán)，返回。掃完所有的點(diǎn)都沒問題，才返回。這里總是忘記，當(dāng)中時(shí)，才否則繼續(xù)循環(huán) 題目：There are a total of n courses you have to take, labeled from 0 to n - 1. Some c...
閱讀 3686·2021-11-12 10:36
閱讀 3831·2021-09-22 15:48
閱讀 3542·2019-08-30 15:54
閱讀 2592·2019-08-29 16:44
閱讀 2363·2019-08-29 16:08
閱讀 2408·2019-08-29 16:06
閱讀 1280·2019-08-29 15:21
閱讀 3171·2019-08-29 12:39
