程序员面试常问的小算法总结( 二 ) _算法

汉诺塔
参考图例：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乘法（公式和下面代码实现的不同，但是原理相同，可以直接背下方代码）

文章插图

在这里插入图片描述
核心语句：
完整代码：
除法
Leetcode原题（用位运算加速了手动除法）
https://blog.csdn.net/qqxx6661/article/details/79723357
为了加速运算，可以依次将被除数减去1，2，4，8，..倍的除数，本质上只是用位运算加速了手动除法