资料来源：https://www.bilibili.com/video/BV1E4411H73v?p=153

一、二分查找算法（非递归）

1、二分查找算法（非递归）介绍

1) 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式
2) 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等) ，将数列排序后再进行查找
3) 二分查找法的运行时间为对数时间 O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n 步，假设从[0,99]的 队列(100 个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂ 100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

2、二分查找算法（非递归）代码实现

数组 { 1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成.

1) 思路分析：
2) 代码实现：

二、分治算法

1、分治算法介绍

1) 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或 相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题 的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序) ，傅立叶变换(快速傅立叶变 换)……
2) 分治算法可以求解的一些经典问题
二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔

2、分治算法的基本步骤

分治法在每一层递归上都有三个步骤：
1) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2) 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3) 合并：将各个子问题的解合并为原问题的解。

3、分治(Divide-and-Conquer(P))算法设计模式如下

4、分治算法最佳实践 - 汉诺塔

汉诺塔的传说
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金 刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小 顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百 亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

汉诺塔游戏的演示和思路分析:

1) 如果是有一个盘， A->C

如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘

2) 先把 最上面的盘 A->B
3) 把最下边的盘 A->C
4) 把 B 塔的所有盘 从 B->C

汉诺塔游戏的代码实现: 看老师代码演示:

三、动态规划算法

1、应用场景 - 背包问题

背包问题：有一个背包，容量为4 磅， 现有如下物品

1) 要求达到的目标为装入的背包的总价值最大，并且重量不超出
2) 要求装入的物品不能重复

2、动态规划算法介绍

1) 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解 的处理算法
2) 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这 些子问题的解得到原问题的解。
3) 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4) 动态规划可以通过填表的方式来逐步推进，得到最优解.

3、动态规划算法最佳实践 - 背包问题

背包问题：有一个背包，容量为4 磅， 现有如下物品

1) 要求达到的目标为装入的背包的总价值最大，并且重量不超出
2) 要求装入的物品不能重复

思路分析和图解
3) 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价 值最大。其中又分 01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)
4) 这里的问题属于 01 背包，即每个物品最多放一个。而无限背包可以转化为 01 背包。
5) 算法的主要思想，利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i]和 v[i]来确定是否需要将该物品 放入背包中。即对于给定的 n 个物品，设v[i]、w[i]分别为第i 个物品的价值和重量，C 为背包的容量。再令v[i][j] 表示在前 i 个物品中能够装入容量为j 的背包中的最大价值。则我们有下面的结果：

6) 图解的分析

4、动态规划 - 背包问题的代码实现

四、KMP 算法

1、应用场景 - 字符串匹配问题

字符串匹配问题：：
1) 有一个字符串 str1= “”硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好”” ，和一个子串 str2=”尚硅谷你尚硅 你”
2) 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回- 1

2、暴力匹配算法

如果用暴力匹配的思路，并假设现在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，则有:

1) 如果当前字符匹配成功（即str1[i] == str2[j]），则i++ ，j++ ，继续匹配下一个字符
2) 如果失配（即 str1[i]! = str2[j]），令i = i - (j - 1) ，j = 0 。相当于每次匹配失败时，i 回溯，j 被置为0。
3) 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量 的时间。(不可行!)
4) 暴力匹配算法实现.
5) 代码

3、KMP 算法介绍

1) KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
2) Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法” ，常用于在一个文本串 S 内查找一个模式串 P 的 出现位置，这个算法由 Donald Knuth 、Vaughan Pratt 、James H. Morris 三人于1977 年联合发表，故取这3 人的 姓氏命名此算法.
3) KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次 回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间
4) 参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

4、KMP 算法最佳应用-字符串匹配问题

字符串匹配问题：：
1) 有一个字符串 str1= “BBC ABCDAB ABCDABCDABDE” ，和一个子串 str2=”ABCDABD”
2) 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回- 1
3) 要求：使用KMP 算法完成判断，不能使用简单的暴力匹配算法.

思路分析图解

看老师代码实现

五、贪心算法

1、应用场景-集合覆盖问题

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区
都可以接收到信号

2、贪心算法介绍

1) 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而 希望能够导致结果是最好或者最优的算法

2) 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解) ，但是都是相对近似(接近)最优解的结果

3、贪心算法最佳应用-集合覆盖

1) 假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有
的地区都可以接收到信号

2) 思路分析:
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假
设总的有 n 个广播台，则广播台的组合总共有
2ⁿ - 1 个,假设每秒可以计算10 个子集， 如图:

使用贪婪算法，效率高:
1) 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择 策略上，因为需要覆盖全部地区的最小集合:
2) 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关 系）
3) 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
4) 重复第 1 步直到覆盖了全部的地区 分析的图解:

3) 代码实现

4、贪心算法注意事项和细节

1) 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解) ，但是都是相对近似(接近)最优解的结果
2) 比如上题的算法选出的是 K1, K2, K3, K5 ，符合覆盖了全部的地区
3) 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果 K2 的使用成本低于 K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的.

六、普里姆算法

1、应用场景 - 修路问题

看一个应用场景和问题：

1) 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3) 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短? 思路: 将 10 条边，连接即可，但是总的里程数不是最小.
正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少.

2、最小生成树

修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree) ，简称 MST。 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
1) N 个顶点，一定有 N-1 条边
2) 包含全部顶点
3) N-1 条边都在图中
4) 举例说明(如图:)
5) 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法

3、普里姆算法介绍

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n- 1)条边包含所有 n 个顶点的
连通子图，也就是所谓的极小连通子图
普利姆的算法如下:

1) 设 G=(V,E)是连通网，T=(U,D)是最小生成树，V,U 是顶点集合，E,D 是边的集合
2) 若从顶点u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U 中，标记顶点 v 的 visited[u]=1
3) 若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将 顶点vj 加入集合 U 中，将边（ui,vj）加入集合 D 中，标记 visited[vj]=1
4) 重复步骤② ，直到 U 与V 相等，即所有顶点都被标记为访问过，此时D 中有n- 1 条边
5) 提示: 单独看步骤很难理解，我们通过代码来讲解，比较好理解.
6) 图解普利姆算法

4、普里姆算法最佳实践(修路问题)

1) 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3) 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
4) 看老师思路分析+代码演示:

七、克鲁斯卡尔算法

1、应用场景-公交站问题

看一个应用场景和问题：

1) 某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
2) 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
3) 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?

2、克鲁斯卡尔算法介绍

1) 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
2) 基本思想：按照权值从小到大的顺序选择 n- 1 条边，并保证这 n- 1 条边不构成回路
3) 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森 林中不产生回路，直至森林变成一棵树为止

3、克鲁斯卡尔算法图解说明

以城市公交站问题来图解说明 克鲁斯卡尔算法的原理和步骤：

4、克鲁斯卡尔最佳实践-公交站问题

看一个公交站问题：

1) 有北京有新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
2) 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
3) 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
4) 代码实现和注解

八、迪杰斯特拉算法

1、应用场景-最短路径问题

看一个应用场景和问题：

1) 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3) 问：如何计算出G 村庄到 其它各个村庄的最短距离?
4) 如果从其它点出发到各个点的最短距离又是多少?

2、迪杰斯特拉(Dijkstra)算法介绍

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以 起始点为中心向外层层扩展(广度优先搜索思想) ，直到扩展到终点为止。

3、迪杰斯特拉(Dijkstra)算法过程

1) 设置出发顶点为v ，顶点集合V{v1,v2,vi…} ，v 到 V 中各顶点的距离构成距离集合 Dis ，Dis {d1,d2,di…} ，Dis 集合记录着v 到图中各顶点的距离(到自身可以看作0 ，v 到vi 距离对应为 di)
2) 从Dis 中选择值最小的di 并移出Dis 集合，同时移出V 集合中对应的顶点vi ，此时的v 到 vi 即为最短路径

3) 更新 Dis 集合，更新规则为： 比较v 到V 集合中顶点的距离值，与v 通过vi 到V 集合中顶点的距离值，保留 值较小的一个(同时也应该更新顶点的前驱节点为 vi ，表明是通过 vi 到达的)
4) 重复执行两步骤，直到最短路径顶点为目标顶点即可结束

4、迪杰斯特拉(Dijkstra)算法最佳应用-最短路径

1) 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3) 问：如何计算出G 村庄到 其它各个村庄的最短距离?
4) 如果从其它点出发到各个点的最短距离又是多少?
5) 使用图解的方式分析了迪杰斯特拉(Dijkstra)算法 思路

6) 代码实现

九、弗洛伊德算法

1、弗洛伊德(Floyd)算法介绍

1) 和 Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法 名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特 ·弗洛伊德命名
2) 弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
3) 迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
4) 弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点 的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每 一个顶点到其他顶点的最短路径。

2、弗洛伊德(Floyd)算法图解分析

1) 设置顶点vi 到顶点vk 的最短路径已知为Lik，顶点vk 到vj 的最短路径已知为Lkj，顶点vi 到vj 的路径为Lij，则 vi 到 vj 的最短路径为：min((Lik+Lkj),Lij) ，vk 的取值为图中所有顶点，则可获得vi 到vj 的最短路径
2) 至于 vi 到vk 的最短路径Lik 或者vk 到vj 的最短路径Lkj ，是以同样的方式获得

3) 弗洛伊德(Floyd)算法图解分析-举例说明

3、弗洛伊德(Floyd)算法最佳应用-最短路径

1) 胜利乡有 7 个村庄(A, B, C, D, E, F, G)
2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
3) 问：如何计算出各村庄到 其它各村庄的最短距离?
4) 代码实现

十、马踏棋盘算法

1、马踏棋盘算法介绍和游戏演示

1) 马踏棋盘算法也被称为骑士周游问题
2) 将马随机放在国际象棋的 8×8 棋盘 Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求 每个方格只进入一次，走遍棋盘上全部 64 个方格
3) 游戏演示: http://www.4399.com/flash/146267_2.htm

2、马踏棋盘游戏代码实现

1) 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
2) 如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了 53 个点，如图：走到了第 53 个，坐标（1,0），发 现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯…… ，思路分析+代码 实现
对第一种实现方式的思路图解

3) 分析第一种方式的问题，并使用贪心算法（greedyalgorithm ）进行优化。解决马踏棋盘问题.

4) 使用前面的游戏来验证算法是否正确。
5) 代码实现