這一期是我打算做的安卓算法面試系列的最后一期了，一來是自從來了美國之后，每天的工作實在太忙了，除了周末之外很少時間能完完整整的總結(jié)一些東西。不過第二個原因，也是最重要的原因，就是在這之后我打算好好沉淀積累一下，等有更多的心得體會再分享出來。
這期我打算聊一聊拓撲排序這個算法。在Java里面具體的實現(xiàn)和一些細節(jié)。這里我盡量不用太多的專業(yè)術(shù)語，用比較通俗的講法來解釋一些概念。（其實是我的狗嘴也吐不出啥象牙。。。以前學(xué)的算法知識早就還給老師了）
其實拓撲排序和廣度優(yōu)先搜索算法在代碼上真的很像，說穿了其實就是圖的遍歷，只不過遍歷的順序和規(guī)則有些少許不同。
相信各位學(xué)習(xí)計算機科學(xué)專業(yè)的同學(xué)應(yīng)該都對高等數(shù)學(xué)或者大學(xué)物理有深刻的陰影。。。我還記得我當(dāng)時考完大學(xué)物理2已經(jīng)覺得自己要掛了，沒忍住給老師打了一個電話求情，雖然最后老師說我離掛科還遠，但是69分的大學(xué)物理2也讓我與那個學(xué)期的獎學(xué)金無緣了。
可能有人問為什么計算機專業(yè)不直接學(xué)Java，C++或者web開發(fā)？一定要先上大學(xué)物理或者高等數(shù)學(xué)？說了這么多廢話，我想說的重點是，每個學(xué)科都有一個自己的課程安排，學(xué)習(xí)一門專業(yè)課之前必須要有一些基礎(chǔ)課程的支撐才行。我們不能不學(xué)高等數(shù)學(xué)和線性代數(shù)直接跳去學(xué)機器學(xué)習(xí)，我們也不能不學(xué)Java或者python直接上手web項目。這也引申出了這一期的內(nèi)容，拓撲排序， 怎么樣在已知某些節(jié)點的前序(prerequisites) 節(jié)點的情況下，把這些節(jié)點的順序排列出來。就好比，我知道一定課程的前后順序的情況下，把我這四年大學(xué)的課程時間安排排列出來，最后打印成課程表。
比如上面這幅圖，我們怎么可以將其課程的依賴關(guān)系，按照先后順利排列起來，這就是拓撲排序可以解決的其中一種，也是最經(jīng)典的問題。
1.怎么定義數(shù)據(jù)結(jié)構(gòu)
首先對于圖來說，我們要知道每個節(jié)點有多少子節(jié)點，也就是后繼節(jié)點，在課程安排例子里面可以理解為，學(xué)了A課程之后可以學(xué)的課程B。那么A就是B的前驅(qū)節(jié)點，B就是A的后繼節(jié)點。
在Java中我們可以使用HashMap來實現(xiàn)，根據(jù)題目的不同，有時候也可以使用別的數(shù)據(jù)結(jié)構(gòu)比如二維數(shù)組。不過我個人比較喜歡HashMap。
那么節(jié)點的關(guān)系可以用一個HashMap來表達，課程使用String 來表示
//節(jié)點的后繼節(jié)點
HashMap<String, HashSet<String>> courses = new HashMap();
同時，在拓撲排序中，我們還需要記錄某個節(jié)點的前驅(qū)節(jié)點的數(shù)量，因為只有當(dāng)某個節(jié)點的前驅(qū)節(jié)點為0的時候，我們才能處理該節(jié)點。對應(yīng)到課程學(xué)習(xí)中，就是只有當(dāng)我們學(xué)習(xí)完畢了某個課程的所有前驅(qū)課程，我們才能學(xué)習(xí)該課程。比如圖中的計算機網(wǎng)絡(luò)課程，需要先學(xué)習(xí)組成原理和通信原理一樣。
//記錄每個點的前驅(qū)節(jié)點數(shù)量
HashMap<String,Integer> preCount = new HashMap<String,Integer>
2.拓撲排序
假設(shè)我們已經(jīng)有了這兩個數(shù)據(jù)結(jié)構(gòu)并且數(shù)據(jù)已經(jīng)填充好了。我們就可以開始進行拓撲排序了。算法很簡單，把前驅(qū)節(jié)點數(shù)量為0的節(jié)點先放入隊列，每次從隊列彈出的時候把自己的后繼節(jié)點的preCount數(shù)量減少1，假如此時后繼節(jié)點的preCount數(shù)量減少到0了，就把節(jié)點加入到隊列中。在這個例子里面，彈出一個節(jié)點的意義就是學(xué)習(xí)一門課程。
這個很好理解，比如我們學(xué)習(xí)完組成原理,距離學(xué)習(xí)計算機網(wǎng)絡(luò)還差一門課。
當(dāng)我們把通信原理學(xué)習(xí)完畢之后，計算機網(wǎng)絡(luò)的前驅(qū)節(jié)點數(shù)量從1減少為0，我們才可以學(xué)習(xí)計算機網(wǎng)絡(luò)。
用代碼來表示的話，如下
//課程調(diào)度隊列
Queue<String> queue = new LinkedList<>();
//最后課程的順序
List<String> sequence = new ArrayList<>();
while (!queue.isEmpty()) {
//獲取當(dāng)前隊列中的第一個課程，將其加入到最后的課程順序列表中
String currentCourse = queue.poll();
sequence.add(currentCourse);
//每當(dāng)一個課程結(jié)束學(xué)習(xí)之后，找到它的后繼課程
for (String course : courses.get(currentCourse)) {
//加入后繼課程的前驅(qū)節(jié)點數(shù)量還是大于0 的，說明該課程還沒被學(xué)習(xí)
if (preCount.get(course) > 0) {
//減少該后繼課程的前驅(qū)節(jié)點數(shù)量
preCount.put(course, preCount.get(course) - 1);
//如果前去梳理減到0，說明我們已經(jīng)可以開始學(xué)習(xí)該課程了，
//加到隊列里面
if (preCount.get(course) == 0) {
queue.add(course);
}
}
}
}
return sequence;
3.和廣度優(yōu)先的不同
其實看代碼大家也可以知道，拓撲排序其實就是廣度優(yōu)先搜索的一種，只不過拓撲排序在插入子節(jié)點到隊列的時候，有一些限制。就是在這里:
if (preCount.get(course) == 0) {
queue.add(course);
}
一般的廣度優(yōu)先只要遍歷了當(dāng)前節(jié)點，就要把當(dāng)前節(jié)點的所有自己點都一股腦的插入到隊列中。在拓撲排序里面，因為每個節(jié)點的前驅(qū)節(jié)點數(shù)量可能會大于1，所以，不能簡單的插入子節(jié)點(或者說后繼節(jié)點)，而是需要額外的數(shù)據(jù)結(jié)構(gòu)，preCount這個HashMap來決定是否可以把后繼節(jié)點插入。
4.有環(huán)？
圖搜索的一個經(jīng)典問題是，如果有環(huán)怎么辦？同樣的，在拓撲排序里面，也可能出現(xiàn)存在環(huán)的情況。比如
在下圖這種情況，學(xué)生就沒辦法學(xué)了。。。。
但是在拓撲排序下面，判斷是否有環(huán)的方法還不太一樣，比如寬度優(yōu)先搜索的情況下，我們可以用一個叫visited的HashSet來記錄已經(jīng)訪問過的節(jié)點。但是拓撲排序不行。
比如下圖這種情況
當(dāng)我們學(xué)習(xí)完A之后，其實我們是不能遍歷完全所有節(jié)點的，因為B和C的前驅(qū)節(jié)點數(shù)量都為1，程序在跑完第一個循環(huán)
while (!queue.isEmpty()) {
//獲取到A
String currentCourse = queue.poll();
sequence.add(currentCourse);
之后，就會直接結(jié)束了。
所以其實我們判斷環(huán)的方法要換成->判斷我們是否能學(xué)習(xí)完所有課程。
HashMap<String, HashSet<String>> courses = new HashMap();
//假如最后我們能學(xué)習(xí)完所有課程
if(result.size() == course.keySet().size()){
return true;
}else{
return false;
}
5.應(yīng)用的范圍
拓撲排序的題目可以出現(xiàn)很多種，但是都是萬變不離其宗，掌握好我們需要的數(shù)據(jù)結(jié)構(gòu)，熟練的寫出廣度優(yōu)先算法的模板代碼， 其實就萬事大吉了。以后比如還有類似的問題，像安裝軟件，比如要安裝A，要先安裝依賴C，等等之類的問題，相信大家都可以迎刃而解了?？偨Y(jié)的來講，一旦我們發(fā)現(xiàn)需要進行對依賴之間進行排序的，用拓撲排序都沒毛病。
6.題目代碼
Leetcode 里面的Course Schedule, 大家可以自己練習(xí)一下。
我沒有講的部分就是數(shù)據(jù)初始化的部分，不過很簡單，大家自己摸索。
我的答案
public int[] findOrder(int numCourses, int[][] prerequisites) {
// record dependecy counts
HashMap<Integer, Integer> dependeciesCount = new HashMap<>();
HashMap<Integer, HashSet<Integer>> dependeciesRelation = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
dependeciesCount.put(i, 0);
dependeciesRelation.put(i, new HashSet<>());
}
for (int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int suf = prerequisites[i][0];
dependeciesCount.put(suf, dependeciesCount.get(suf) + 1);
dependeciesRelation.get(pre).add(suf);
}
Queue<Integer> queue = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : dependeciesCount.entrySet()) {
if (entry.getValue() == 0) {
queue.add(entry.getKey());
}
}
int[] index = new int[numCourses];
int currentIndex = 0;
while (!queue.isEmpty()) {
Integer currentCourse = queue.poll();
index[currentIndex] = currentCourse;
currentIndex++;
for (Integer nei : dependeciesRelation.get(currentCourse)) {
if (dependeciesCount.get(nei) > 0) {
dependeciesCount.put(nei, dependeciesCount.get(nei) - 1);
if (dependeciesCount.get(nei) == 0) {
queue.add(nei);
}
}
}
}
int[] empty = {};
return currentIndex == numCourses ? index : empty;
}
后記
最后一期算法教程寫完了，其實感覺如果大家能把這7個大塊給充分理解，面對大部分的公司的算法面試其實也沒多大問題了。這也是我2017年-2018年初面試各個公司的算法題的一些心得體會。
雖然我的標(biāo)題一直都是以面試 開頭，但是我覺得最重要的還是學(xué)習(xí)，或者說是復(fù)習(xí)算法的這個過程。去理解去學(xué)習(xí)的這個過程才是精髓。當(dāng)然，這些內(nèi)容也是上學(xué)就應(yīng)該學(xué)好的，現(xiàn)在重新復(fù)習(xí)，也算是還債(technical debt)。。。。
回頭看這個系列的初衷，也是希望大家在面對面試的同時，能回顧一些以前上學(xué)時候的知識,做到溫故而知新。只要讀者看了我的文章，能發(fā)出一種“挖槽這個以前好像學(xué)過啊”的感嘆，我也就滿足了~
2019年對我來說是一個新的起點，我也要不停的督促自己好好工作，多反思多學(xué)習(xí)，以后爭取能分享更多高質(zhì)量的文章和知識。希望自己永遠不要忘掉當(dāng)初雄心壯志面試硅谷公司的那顆赤子之心。
