程序員面試常問的小算法總結-魔扣目錄

圖的最短路徑算法

Floyd最短路算法（多源最短路）

參考：https://www.cnblogs.com/ahalei/p/3622328.html

在這里插入圖片描述

上圖中有4個城市8條公路，公路上的數字表示這條公路的長短。請注意這些公路是單向的。我們現在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題。

現在需要一個數據結構來存儲圖的信息，我們仍然可以用一個4*4的矩陣（二維數組e）來存儲。

在這里插入圖片描述

核心代碼：

這段代碼的基本思想就是：

最開始只允許經過1號頂點進行中轉，接下來只允許經過1和2號頂點進行中轉……允許經過1~n號所有頂點進行中轉，求任意兩點之間的最短路程。用一句話概括就是：從i號頂點到j號頂點只經過前k號點的最短路程。

Dijkstra最短路算法（單源最短路）

參考：http://blog.51cto.com/ahalei/1387799

指定一個點（源點）到其余各個頂點的最短路徑，也叫做“單源最短路徑”。例如求下圖中的1號頂點到2、3、4、5、6號頂點的最短路徑。

在這里插入圖片描述

仍然使用二維數組e來存儲頂點之間邊的關系，初始值如下。

在這里插入圖片描述

我們還需要用一個一維數組dis來存儲1號頂點到其余各個頂點的初始路程，如下。

在這里插入圖片描述

將此時dis數組中的值稱為最短路的“估計值”。

既然是求1號頂點到其余各個頂點的最短路程，那就先找一個離1號頂點最近的頂點。通過數組dis可知當前離1號頂點最近是2號頂點。當選擇了2號頂點后，dis[2]的值就已經從“估計值”變為了“確定值”，即1號頂點到2號頂點的最短路程就是當前dis[2]值。

既然選了2號頂點，接下來再來看2號頂點有哪些出邊呢。有2->3和2->4這兩條邊。先討論通過2->3這條邊能否讓1號頂點到3號頂點的路程變短。也就是說現在來比較dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1號頂點到3號頂點的路程。dis[2]+e[2][3]中dis[2]表示1號頂點到2號頂點的路程，e[2][3]表示2->3這條邊。所以dis[2]+e[2][3]就表示從1號頂點先到2號頂點，再通過2->3這條邊，到達3號頂點的路程。

這個過程有個專業術語叫做“松弛”。松弛完畢之后dis數組為：

在這里插入圖片描述

接下來，繼續在剩下的3、4、5和6號頂點中，選出離1號頂點最近的頂點4，變為確定值，以此類推。

在這里插入圖片描述

最終dis數組如下，這便是1號頂點到其余各個頂點的最短路徑。

在這里插入圖片描述

M：邊的數量
N：節點數量

通過上面的代碼我們可以看出，這個算法的時間復雜度是O(N^2)。其中每次找到離1號頂點最近的頂點的時間復雜度是O(N)

優化:

這里我們可以用“堆”（以后再說）來優化，使得這一部分的時間復雜度降低到O(logN)。
另外對于邊數M少于N^2的稀疏圖來說（我們把M遠小于N^2的圖稱為稀疏圖，而M相對較大的圖稱為稠密圖），我們可以用鄰接表來代替鄰接矩陣，使得整個時間復雜度優化到O( (M+N)logN)。
請注意！在最壞的情況下M就是N^2，這樣的話MlogN要比N^2還要大。但是大多數情況下并不會有那么多邊，因此(M+N)logN要比N2小很多。

用鄰接表代替鄰接矩陣存儲

參考：http://blog.51cto.com/ahalei/1391988

略微難懂，請參考原文

總結如下：

可以發現使用鄰接表來存儲圖的時間空間復雜度是O(M)，遍歷每一條邊的時間復雜度是也是O(M)。如果一個圖是稀疏圖的話，M要遠小于N^2。因此稀疏圖選用鄰接表來存儲要比鄰接矩陣來存儲要好很多。

漢諾塔

參考圖例：https://www.zhihu.com/question/24385418/answer/89435529

關鍵代碼：

楊輝三角

參考：https://blog.csdn.net/zmy_3/article/details/51173580

關鍵代碼（巧用Python中的yield）：

注釋：N加上一個0之后，最后一個數是1+0，直接就等于1，不會有0

回文數/回文串

解法一：暴力

解法二：分字符串和數字

斐波拉契數列(Fibonacci)

最大子序列與最大子矩陣問題

數組的最大子序列問題

給定一個數組，其中元素有正，也有負，找出其中一個連續子序列，使和最大。

參考自己的博客：https://blog.csdn.net/qqxx6661/article/details/78167981

可以理解為動態規劃：

可以用標準動態規劃求解也可以用直接方法求解，但思路都是動態規劃

最大子矩陣問題

給定一個矩陣（二維數組），其中數據有大有小，請找一個子矩陣，使得子矩陣的和最大，并輸出這個和。

參考：https://blog.csdn.net/kavu1/article/details/50547401

思路：

原始矩陣可以是二維的。假設原始矩陣是一個3 * n 的矩陣，那么它的子矩陣可以是 1 * k, 2 * k, 3 * k，（1 <= k <= n）。如果是1*K，這里有3種情況：子矩陣在第一行，子矩陣在第二行，子矩陣在第三行。如果是 2 * k，這里有兩種情況，子矩陣在第一、二行，子矩陣在第二、三行。如果是3 * k，只有一種情況。

為了能夠找出最大的子矩陣，我們需要考慮所有的情況。假設這個子矩陣是 2 * k, 也就是說它只有兩行，要找出最大子矩陣，我們要從左到右不斷的遍歷才能找出在這種情況下的最大子矩陣。如果我們把這兩行上下相加，情況就和求“最大子段和問題” 又是一樣的了。

KMP算法

原理參考：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

移動位數 = 已匹配的字符數 - 對應的部分匹配值

"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。以"ABCDABD"為例，

實現參考自己的博客：

https://blog.csdn.net/qqxx6661/article/details/79583707

LCS/最長公共子序列/最長公共子串

參考自己的博客：

https://blog.csdn.net/qqxx6661/article/details/79587392

最長公共子序列LCS

動態規劃狀態轉移方程式

在這里插入圖片描述

最長公共回文子串

動態規劃狀態轉移方程式

在這里插入圖片描述

求圓周率

在這里插入圖片描述

大數問題（加減乘除）

加法

對應位置相加，考慮進位，前面不夠補0

減法

和相加十分類似

就是按照我們手寫除法時的方法，兩個數字末位對齊，從后開始，按位相減，不夠減時向前位借一。
最終結果需要去除首端的0.如果所有位都是0，則返回0。

乘法

大數乘法問題及其高效算法：

https://blog.csdn.net/u010983881/article/details/77503519

方法：

模擬小學乘法：最簡單的乘法豎式手算的累加型；

自己實現的：https://blog.csdn.net/qqxx6661/article/details/78119074

分治乘法：最簡單的是Karatsuba乘法，一般化以后有Toom-Cook乘法；

見下方

快速傅里葉變換FFT：（為了避免精度問題，可以改用快速數論變換FNTT），時間復雜度O(N lgN lglgN)。具體可參照Schönhage–Strassen algorithm；
中國剩余定理：把每個數分解到一些互素的模上，然后每個同余方程對應乘起來就行；
Furer’s algorithm：在漸進意義上FNTT還快的算法。不過好像不太實用，本文就不作介紹了。大家可以參考維基百科

方法2：

參考：

https://blog.csdn.net/jeffleo/article/details/53446095

Karatsuba乘法（公式和下面代碼實現的不同，但是原理相同，可以直接背下方代碼）