程序员面试常问的小算法总结
前言
本文快速回顾了面试常考的算法，用作面试复习，事半功倍。
需要说明的是，由于算法的代码实现主要注重思路的清晰，下方有代码实现的文章主要以Python为主，Java为辅，对于Python薄弱的同学敬请不用担心，几乎可以看作是伪代码，可读性比较好。如实在有困难可以自行搜索Java代码
此外，关于算法的文章之后也会单独开设算法专栏进行总结，敬请期待。
面试知识点复习手册
全复习手册文章导航
全复习手册文章导航(CSDN)
已发布知识点复习手册
Java基础知识点面试手册
Java容器（List、Set、Map）知识点快速复习手册
Java并发知识点快速复习手册（上）
Java并发知识点快速复习手册（下）
Java虚拟机知识点快速复习手册（上）
Java虚拟机知识点快速复习手册（下）
快速梳理23种常用的设计模式
Redis基础知识点面试手册
Leetcode题解分类汇总（前150题）
面试常问的小算法总结
查找算法总结及其部分算法实现Python/Java
排序算法实现与总结Python/Java
HTTP应知应会知识点复习手册（上）
HTTP应知应会知识点复习手册（下）
......等（请查看全复习手册导航）
-----正文开始-----
图的最短路径算法
Floyd最短路算法（多源最短路）
参考：https://www.cnblogs.com/ahalei/p/3622328.html
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。
核心代码：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：
最开始只允许经过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号顶点到其余各个顶点的最短路径。
//Dijkstra算法核心语句
for(i=1;i<=n-1;i++)
{
//找到离1号顶点最近的顶点
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0 && dis[j] { min=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[u][v] { if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } M：边的数量 N：节点数量 通过上面的代码我们可以看出，这个算法的时间复杂度是O(N^2)。其中每次找到离1号顶点最近的顶点的时间复杂度是O(N) 优化: 这里我们可以用“堆”（以后再说）来优化，使得这一部分的时间复杂度降低到O(logN)。 另外对于边数M少于N2的稀疏图来说（我们把M远小于N2的图称为稀疏图，而M相对较大的图称为稠密图），我们可以用邻接表来代替邻接矩阵，使得整个时间复杂度优化到O( (M+N)logN)。 请注意！在最坏的情况下M就是N2，这样的话MlogN要比N2还要大。但是大多数情况下并不会有那么多边，因此(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 关键代码： def move(n,a,b,c): if n == 1: print(a, "--->", c) else: move(n-1,a,c,b) print(a, "--->", c) move(n-1,b,a,c) 杨辉三角 参考：https://blog.csdn.net/zmy_3/article/details/51173580 关键代码（巧用python中的yield）： 注释：N加上一个0之后，最后一个数是1+0，直接就等于1，不会有0 def triangles(): N=[1] while True: yield N N.append(0) N=[N[i-1] + N[i] for i in range(len(N))] n=0 for t in triangles(): print(t) n=n+1 if n == 10: break 回文数/回文串 解法一：暴力 return a == a[::-1] 解法二：分字符串和数字 # 字符串/数字 a = len(s) i = 0 while i <= (a/2): if s[i] == s[a-1-i]: i += 1 else: return False return True # 数字 def isPalindrome(x): if x < 0: return False temp = x y = 0 while temp: y = y*10 + temp%10 temp /= 10 return x == y 斐波拉契数列(Fibonacci) def fibonacci(): # 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 f = [0] * MAXSIZE f[0] = 1 f[1] = 1 for i in range(2, MAXSIZE): f[i] = f[i-1] + f[i-2] return f fibs = [1,1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 最大子序列与最大子矩阵问题 数组的最大子序列问题 给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。 参考自己的博客：https://blog.csdn.net/qqxx6661/article/details/78167981 可以理解为动态规划： dp[i] = dp[i-1] + s[i] (dp[i-1] >= 0) dp[i] = s[i] (dp[i-1] < 0) 可以用标准动态规划求解也可以用直接方法求解，但思路都是动态规划 最大子矩阵问题 给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。 参考：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–Morris–Pratt_algorithm.html 移动位数 = 已匹配的字符数 - 对应的部分匹配值 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例， － "A"的前缀和后缀都为空集，共有元素的长度为0； － "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0； － "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； － "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； － "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1； － "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2； － "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。 实现参考自己的博客： https://blog.csdn.net/qqxx6661/article/details/79583707 LCS/最长公共子序列/最长公共子串 参考自己的博客： https://blog.csdn.net/qqxx6661/article/details/79587392 最长公共子序列LCS 动态规划状态转移方程式 最长公共回文子串 动态规划状态转移方程式 求圆周率 from random import random from math import sqrt from time import clock #计算程序运行时间 DARTS=1200 #抛洒点的个数 #DARTS=5000 #DARTS=20000 #DARTS=1000000 hists=0 #抛洒点在1/4(半径为1)圆内点的个数 clock() for i in range(1,DARTS): x,y=random(),random() dict=sqrt(x**2+y**2) if dict<=1.0: hists=hists+1 #随机设点，若抛洒点在1/4圆内，则dice+1 pi=4*(hists/DARTS) print("PI的值是 %s" %pi) print("程序运行的时间是 %-5.5ss" %clock()) 大数问题（加减乘除） 加法 对应位置相加，考虑进位，前面不够补0 L1 = "2649821731631836529481632803462831616487712734074314936141303241873417434716340124362304724324324324324323412121323164329751831" L2 = "1045091731748365195814509145981509438583247509149821493213241431431319999999999999999999999999999999999999999999999999341344779" # 长度强行扭转到一致，不够前面补0 max_len = len(L1) if len(L1) > len(L2) else len(L2) l1 = L1.zfill(max_len) l2 = L2.zfill(max_len) a1 = list(l1) a2 = list(l2) # 99+99最大3位所以多一位 result_list = [0] * (max_len + 1) # 长度一致 每个对应的位置的相加的和 %10 前一位补1 如果>10 否则0 for index in range(max_len - 1, -1, -1): index_sum = result_list[index + 1] + int(a1[index]) + int(a2[index]) less = index_sum - 10 result_list[index + 1] = index_sum % 10 result_list[index] = 1 if less >= 0 else 0 # 若第一位为0，去除 if result_list[0] == 0: result_list.pop(0) # 转为str的list result = [str(i) for i in result_list] print(''.join(result)) 减法 和相加十分类似 就是按照我们手写除法时的方法，两个数字末位对齐，从后开始，按位相减，不够减时向前位借一。 最终结果需要去除首端的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乘法（公式和下面代码实现的不同，但是原理相同，可以直接背下方代码） 核心语句： long z2 = karatsuba(a, c); long z0 = karatsuba(b, d); long z1 = karatsuba((a + b), (c + d)) - z0 - z2; return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0); 完整代码： /** * Karatsuba乘法 */ public static long karatsuba(long num1, long num2){ //递归终止条件 if(num1 < 10 || num2 < 10) return num1 * num2; // 计算拆分长度 int size1 = String.valueOf(num1).length(); int size2 = String.valueOf(num2).length(); int halfN = Math.max(size1, size2) / 2; /* 拆分为a, b, c, d */ long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN)); long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN)); long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN)); long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN)); // 计算z2, z0, z1, 此处的乘法使用递归 long z2 = karatsuba(a, c); long z0 = karatsuba(b, d); long z1 = karatsuba((a + b), (c + d)) - z0 - z2; return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0); } 除法 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为图中的边数 # coding=utf-8 import sys class Graph(object): def __init__(self, maps): self.maps = maps self.nodenum = self.get_nodenum() self.edgenum = self.get_edgenum() def get_nodenum(self): return len(self.maps) def get_edgenum(self): count = 0 for i in range(self.nodenum): for j in range(i): if self.maps[i][j] > 0 and self.maps[i][j] < 9999: count += 1 return count def kruskal(self): res = [] if self.nodenum <= 0 or self.edgenum < self.nodenum - 1: return res edge_list = [] for i in range(self.nodenum): for j in range(i, self.nodenum): if self.maps[i][j] < 9999: edge_list.append([i, j, self.maps[i][j]]) # 按[begin, end, weight]形式加入 edge_list.sort(key=lambda a: a[2]) # 已经排好序的边集合 group = [[i] for i in range(self.nodenum)] for edge in edge_list: for i in range(len(group)): if edge[0] in group[i]: m = i if edge[1] in group[i]: n = i if m != n: res.append(edge) group[m] = group[m] + group[n] group[n] = [] return res def prim(self): res = [] if self.nodenum <= 0 or self.edgenum < self.nodenum - 1: return res res = [] seleted_node = [0] candidate_node = [i for i in range(1, self.nodenum)] while len(candidate_node) > 0: begin, end, minweight = 0, 0, 9999 for i in seleted_node: for j in candidate_node: if self.maps[i][j] < minweight: minweight = self.maps[i][j] begin = i end = j res.append([begin, end, minweight]) seleted_node.append(end) candidate_node.remove(end) return res if __name__ == "__main__": # 读取第一行的n n = int(sys.stdin.readline().strip('')) cun_list = list(map(int,sys.stdin.readline().strip('').split(' '))) dp = [[0 for __ in range(n)] for __ in range(n)] for i in range(n): for j in range(n): if i == j: dp[i][j] = 0 continue dp[i][j] = max(cun_list[i],cun_list[j]) print(dp) graph = Graph(dp) # print('邻接矩阵为\n%s' % graph.maps) # print('节点数据为%d，边数为%d\n' % (graph.nodenum, graph.edgenum)) # print('------最小生成树kruskal算法------') # print(graph.kruskal()) # print('------最小生成树prim算法') # print(graph.prim()) print() -----正文结束----- 关注我 我是蛮三刀把刀，目前为后台开发工程师。主要关注后台开发，网络安全，Python爬虫等技术。 来微信和我聊聊：yangzd1102 Github：https://github.com/qqxx6661 原创博客主要内容 笔试面试复习知识点手册 Leetcode算法题解析（前150题） 剑指offer算法题解析 Python爬虫相关技术分析和实战 后台开发相关技术分析和实战 同步更新以下博客 1. Csdn http://blog.csdn.net/qqxx6661 拥有专栏：Leetcode题解（Java/Python）、Python爬虫开发、面试助攻手册 2. 知乎 https://www.zhihu.com/people/yang-zhen-dong-1/ 拥有专栏：码农面试助攻手册 3. 掘金 https://juejin.im/user/2119514149109095 4. 简书 https://www.jianshu.com/u/b5f225ca2376 个人公众号：Rude3Knife 如果文章对你有帮助，不妨收藏起来并转发给您的朋友们~