程序员面试常问的小算法总结

图的最短路径算法

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

方法：

1. 模拟小学乘法：最简单的乘法竖式手算的累加型；

自己实现的：https://blog.csdn.net/qqxx6661/article/details/78119074

2. 分治乘法：最简单的是Karatsuba乘法，一般化以后有Toom-Cook乘法；

见下方

3. 快速傅里叶变换FFT：（为了避免精度问题，可以改用快速数论变换FNTT），时间复杂度O(N lgN lglgN)。具体可参照Schönhage–Strassen algorithm；
4. 中国剩余定理：把每个数分解到一些互素的模上，然后每个同余方程对应乘起来就行；
5. Furer’s algorithm：在渐进意义上FNTT还快的算法。不过好像不太实用，本文就不作介绍了。大家可以参考维基百科

方法2：

参考：

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

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

在这里插入图片描述

核心语句：

完整代码：

除法

Leetcode原题（用位运算加速了手动除法）

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

为了加速运算，可以依次将被除数减去1，2，4，8，..倍的除数，本质上只是用位运算加速了手动除法

计算机计算乘除法的原理

位运算除法

https://blog.csdn.net/zdavb/article/details/47108505

最小生成树

图解Prim算法和Kruskal算法：

https://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

两种方法的时间复杂度

Prim：

这里记顶点数v，边数e

• 邻接矩阵:O(v2)
• 邻接表:O(elog2v)

Kruskal：

elog2e e为图中的边数