本文主要是介绍【程序员必会10大算法】 1.2分查找 2.分治 3.动态规划 4.kmp 5.贪心 6.prim 7.kruskal 8.dijkstra 9.floyd 10.马踏棋盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
程序员常用的10个算法：
1)2分查找
场景：非递归的二分查找。
(1)之前讲过递归算法. 非递归反而更好理解。
(2)需要先保证数组有序.
2)dac(divide and conquer分治算法)
(1)分治算法使用场景：
傅里叶变换
二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
(2)如何分、如何治:
看成2部分，AB为1个部分，C为一个部分，那么就是AB移动到b位置，C移动到c位置，AB移动到c位置.
先把最上面的盘A--》B
把最下面的盘A--》C
把B塔的所有盘，从B--》C
(3)没有思想，不知道如何拆分是难点. 先有思想，然后把思想转为代码。
3)dynamic(动态规划)
场景： 01背包问题
(1)把大的问题划分为小的问题，从而一步步获取最优解的处理算法
(2)动态规划与分治不同的是：
适用于动态规划求解的问题，经分解得到子问题往往不是独立的。
下一个子阶段的求解是建立在上一个子阶段的解的基础上。 而 分治在2个盘和3个盘的移动是没有什么关系的，是独立的问题。
(3)动态规划是：填表的方式实现的。
思想--》公式--》水到渠成。和数学也没有什么关系。
w[i]: 第i的商品的重量
v[i]: 第i个商品的价值
v[i][j]: 表示在前i个物品中能够装入容量为j
v[i][0] = v[0][j] = 0
// 当准备加入新增的商品的容量 大于 当前背包的容量时，就直接使用上一个单元格的装入情况
w[i] > j时，v[i][j] = v[i-1][j];
// 当尊卑加入的新增的商品的容量小于等于当前背包的容量
// 装入的方式: v[i-1][j]: 就是上一个单元格的装入的最大值
// v[i]: 当前商品的价值v[i-1][j-w[i]]: 装入i-1商品，到剩余空间j-w[i]的最大值
j >= w[i]时，v[i][j] = max(v[i-1][j], v[i] + v[i-1][j-w[i]])
4)kmp
(1)暴力匹配
场景： 有一次匹配不成功时，有大量的回溯
(2)kmp的思路
next数组：保存模式串中前后最长公共子序列的长度，每次回溯时。
字符串的前缀和后缀的最长公共部分。 --》部分搜索词
要充分利用： 部分匹配表
部分匹配表是如何产生的？
但是：kmp的核心思想是：不要暴力匹配。 而是有个算法，把没有必要匹配的跳过。
前缀： 从前面开始。 后缀：从后面开始 如：ABCDEFG Axxx xxxG， 这样匹配。
5)greedy(贪心)
场景： 集合覆盖问题
(1)引入：广播台覆盖。
(2)贪心算法说明：
每一步选择中都选择最好或者最优的选择，从而希望结果是最好或者最优的。
但是贪心算法未必是最优解，但是都是对近似最优解的结果。
(3)贪心算法怎么来的?
1.找一个覆盖了最多未覆盖的地区的电台.
2.不断把选择过的去掉，然后比较其它剩余地方的价值
(4)每次就选择最好的，这就体现出贪婪的特性
(5)贪婪法 对比：穷举法
效率非常低，甚至计算不出来。N个电台的选择就有：2的N次方-1 种选择办法。
6)prim
场景： 修路问题--》 求最小生成树的算法。
已知：7个村庄 和 每个村庄之间的距离。
求：如何修路公里最短 且 各个村庄都连通。
(1)最基本的思路： 直接把10条边连接起来。 但是很可能不是最短。
(2)正确思路：尽可能的选择少的路线，并且每条路线最小，这样才能保证总里程数最小。
(3)最小生成树MST：
主要是：普利姆 和 克鲁斯卡尔 算法。 就类似于： 我要去从郑州到北京。。我就坐高铁经过了河北，然后再到北京，是可以绕过一站再到。
(4)思路：7个点，肯定要修6条路。
先从A顶点开始，遍历周围的几个顶点。 先得到AG最小。
再把AG周围的没有访问过的顶点加入进来，找到B
AGB顶点，寻找周围的，
(5)解决修路问题生成图
1.先建立起来图
2.不断计算，然后标记
7)kruskal
场景：公交站问题--》和Prim算法一样，另外一个求 加权连通图的最小生成树的算法。
(1)核心：
1.边权值排序(冒泡、选择、插入)
2.不停加入到森林，判断是否产生回路。
8)dijkstra
场景：最短路径问题。
算法比较麻烦。
(1)一个点，到另外一个点的最短距离是多少.A-->B 可能有几条路线，选择哪个路线最短。
(2)用到了广度优先的搜索思想，直到扩展到终点为止。 这样当然可以知道一个点到另外一个点的距离。
(3)dis集合记录的是：v这个出发点到各个顶点的距离。 最后的结果必然记录在dis中。
大V代表访问过的顶点。
pre_visited: 记录各个顶点的前驱顶点是哪一个，也就是上一次是从哪个顶点访问到自己的。
already_arr:
(4)比Prim和Kruskal算法稍微困难一点。 使用的是广度优先算法。 用于解决： 最短路径问题。
9)floyd
场景：和Dijkstra一样，是一种用于寻找给定的加权图中顶点间最短路径的算法。
算法比较巧妙，也比较好写。 但是算法复杂度比较高。
与dj的区别：可以求出各个顶点之间的最短路径。 dj是计算某个顶点到其它顶点的最短路径。
(1)min((Lik + Lkj), Lij)
把A作为中间顶点的所有情况进行遍历。
实现: 3层for循环. 把所有情况进行遍历，并进行更新。
时间复杂度: N的3次方。
把每个顶点作为处罚顶点进行遍历，遍历的时候，不停的更新距离表和前驱关系表。
10)horse(马踏棋盘算法)--》DFS
场景：骑士周游的小游戏问题
(1)每个方格走一次，马走日，只能走一遍，把所有的格子走一遍。
(2)给一个马的初始位置，马怎样走才能把棋盘走完。
(3)图的深度优先搜索DFS的应用
(4)回溯的体现：以8*8=64个格子为例子，加入走到了第53个，坐标为(1,0)，发现已经走到了尽头，
没办法，那就只能回退了，查看其它的路径，就在棋盘上不停的回溯。。。
(5)优化(22s-->35ms 优化很多倍)
(1)策略不同，会影响快慢
(2)使用贪心算法对原来的算法进行优化:
1.获取当前位置，可以下一步走的位置的集合
2.对每一个位置能走的下一步进行非递减排序: 1 2 2 3 3 4 5 6 6 7... 允许有重复的值
这篇关于【程序员必会10大算法】 1.2分查找 2.分治 3.动态规划 4.kmp 5.贪心 6.prim 7.kruskal 8.dijkstra 9.floyd 10.马踏棋盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
