今天總結(jié)這四道題目

無重復(fù)字符的最長子串

這題已經(jīng)做了多次，但是今天做的時候發(fā)現(xiàn)了一個我之前有點沒有重視的地方。我們通過HashMap來記錄重復(fù)的字符出現(xiàn)的下標(biāo)，然后為了加快算法執(zhí)行，如果發(fā)生重復(fù)，我們會將子字符串開始的下標(biāo)記作從Hashmap中取出的下標(biāo)+1.但是這里一定要注意，判斷重復(fù)的字符和當(dāng)前的字符串開始的下標(biāo)的大小，不然有可能出現(xiàn)【往回拉】的情況，導(dǎo)致最后出錯。

概率最大的路徑

這實際上是地杰斯特拉算法的變體。

求一個單源最短路徑問題。算法主要分成這樣幾個方面：

1. 構(gòu)建帶權(quán)圖的數(shù)據(jù)結(jié)構(gòu)：我們通過List<List<Pair>>來存儲節(jié)點以及邊上的權(quán)值信息。

2. 迪杰斯特拉算法其實就是一個BFS+貪心的過程，所以下一個需要遍歷到的節(jié)點，應(yīng)該使得當(dāng)前的概率最大。我們可以使用優(yōu)先隊列。

3. 開辟一個數(shù)組記錄從起始點到當(dāng)前的點的概率值，只有大于這個概率才可以被加入隊列（不然肯定有更好的路徑，不走重復(fù)的道路）

代碼如下：

課程表I

我們首先需要對問題有一個了解：

1. 這是一個圖問題，這個圖可能有很多子圖

2. 只要每一個子圖中不存在環(huán)就行

可以使用拓?fù)渑判?，也可以使用dfs。我這里使用的dfs，思路主要是這樣：

visited表示當(dāng)前的節(jié)點訪問的情況，0 表示沒有訪問過，1表示已經(jīng)訪問了。同時我們還需要使用另外一個值：-1.因為我們在考察課程是否會形成環(huán)路的時候，我們開始的節(jié)點可能是一個大圖中的一部分，所以visited數(shù)組需要傳遞，但是我們直接記錄為1的話無法區(qū)分是在本次的dfs中出現(xiàn)了重復(fù)，還是咋地，所以我們使用-1表示在其他的dfs中已經(jīng)訪問過，而且沒有環(huán)路（不然直接返回false了）

代碼如下：

課程表II

這個問題雖然題目中沒有指出，但是其實還是需要判斷是否存在環(huán)。其實這個問題很明顯就是拓?fù)渑判騿栴}。我們首先記錄每一個點的出度，出度為0的點，一定是最先需要上的課。在構(gòu)建表的時候也注意需要反向構(gòu)建路徑。首先將出度為0的點加入隊列，然后從隊列中彈出，并且將它指向的節(jié)點的出度都--，然后將出度為0的節(jié)點加入隊列。如果最后所有的點都能被彈出，說明不存在環(huán)。而且我們也可以形成一個結(jié)果：

最長的回文子串

這道題我才用的方式是中心擴散法：