做开发的对于算法这个词都不陌生，每当谈论到某人是个算法工程师，某人写了个什么厉害的算法。都会不由得对他产生敬意，有人说，程序=数据结构+算法。虽然有失偏颇，但足以体现出算法的重要性。那什么是算法呢，它可以是一个公式，一个食谱，一本操作手册，其实在没有电脑之前，就已经有算法了，算法是解决特定问题的方法步骤的描述。在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法思想有很多，业界公认的常用算法思想有八种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然八种只是一个大概的划分，是一个“仁者见仁、智者见智”的问题。最近在力扣上看到不少精妙的解题思路，不禁想对算法常见的解题思路做一个总结。故有此文
算法的基本特征
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。对于算法而言，实现的语言并不重要，重要的是思想。一个正确的算法具备以下五个基本特征
- 输入: 算法具有0个或多个输入
- 输出: 算法至少有1个或多个输出
- 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性：算法中的每一步都有确定的含义，不会出现二义性
- 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
1.枚举思想
基本思想
枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。
方法特征
- 确定枚举对象、枚举范围和判定条件。
- 逐一列举可能的解，验证每个解是否是问题的解。
基本步骤
- 确定枚举对象（即问题解的表达形式，一般需要用若干参数来描述）
- 逐一列举可能（根据枚举对象的参数构造循环，一一列举其表达式的每一种取值情况）
- 逐一验证可能解（ 根据问题解的要求，验证枚举对象表达式的每一个取值，如果满足条件，则采纳它，否则抛弃之。）
经典例子
- 百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求用100元买100只鸡,各为多少才合适
- 水仙花数问题：输出所有的“水仙花数”，所谓的“水仙花数”是指一个三位数其各位数字的立方和等于该数本身，例如153是“水仙花数”，因为：153 = 1^3 + 5^3 + 3^3。
- 鸡兔同笼问题：今有鸡兔同笼，上有三十五头，下有九十四足。问鸡兔各几只？
2.递推思想
基本思想
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
思想特征
递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推 算法。
- 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
- 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。
3.递归思想
思维策略
在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。递归过程一般通过函数或子过程来实现。递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
方法特征
- 递归是在过程或函数中调用自身的过程。
- 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
- 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
- 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。
经典例子
- 斐波那契数列：斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次类推下去，你会发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。数列规律是下一个数等于前两个数的和（递归）
- 汉诺塔：超经典了的递归解决问题例子，法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
4.分治思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
基本思想
“分而治之”，大问题能够拆成相似的小问题，记住这些小问题需要具有相似性。而后将小问题的每个解合成为大问题的解。所以说大问题如何拆，小问题如何合并才是这个算法最主要的一个思想。实际上很多算法如贪心算法，动态规划等等都是要求把大问题拆成小问题。而分治算法的重要一点就是要适用于能够重新把小问题的解合并为大问题的解。
方法特征
- 该问题的规模缩小到一定的程度就可以容易地解决
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
基本步骤
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
经典例子
- 快速排序：这个就不用多说了吧。。
- Strassen矩阵乘法 ：矩阵乘法，一般代码实现需要做三次循环，其时间复杂度就是O(n^3)。strassen提出的Strassen矩阵乘法，最终把复杂度降低为O( n^lg7 ) ≈ O( n^2.81 )；别小看这个细微的改进，当n非常大时，该算法将比平凡算法节约大量时间。这个算法种就使用到分治思想
- 棋盘覆盖问题
- 线性时间选择问题
- 循环赛日程表
5.动态规划
每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
基本思想
将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
方法特征
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
基本步骤：
分析最优解的性质，并刻画其结构特征。
递归的定义最优解。
以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
根据计算最优值时得到的信息，构造问题的最优解
经典例子
- 剪绳子问题 ：给你一根长度为N的绳子，请把绳子剪成M段（m,n都是整数），每段绳子的 长度记为k[0],k[1],k[2]….请问如何剪绳子使得k[0],k[1],k[2] 的乘积最大 。例如 绳子长度8 最大乘积18 = 233
- 硬币问题 ：我们有面值为1元3元5元的硬币若干枚，如何用最少的硬币凑够11元？
- 最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）问题： 给定两个序列（两个字符串），求出它们的最长公共子序列（公共子字符串）。注意：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最长公共子序列，但不是它们的最长公共字串。而 S1 = ABCD，S2=AEBD，那么S1与S2的最长公共子序列是{ABD}。
6.贪心法
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
基本思想
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
基本步骤：
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
经典例子
- 钱币找零问题：假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？
- 股票问题：假设你有一个数组，其中第i个元素是某只股票在第i天的价格。如你最多只获准完成一项交易(即，买一股，卖一股)，设计一个算法来寻找最大的利润。注意，你不能在买股票之前卖掉它。
- 小船过河问题
- 区间覆盖问题
- Huffman编码
- Dijkstra算法（求解最短路径）
- 最小生成树算法
7.回溯法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。对于回溯法所用到的核心思想就是递归法。回溯法也是经典的人工智能的基础，这句话中”经典”可以理解为”传统”。现如今，人工智能领域有一个非常流行的话题，那就是机器学习。
方法特征
- 针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
- 确定结点的扩展搜索规则
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
经典例子
八皇后问题：该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
迷宫问题：定义一个二维数组如下
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
图的着色问题：又称着色问题，是最著名的NP-完全问题之一。其数学定义为：给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。
连续邮资问题：假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在一张信封上可以贴出从邮资1开始，增量为1的最大连续邮资区间。
符号三角形问题：由14个“+”号和14个“-”号组成的符号三角形。2个相邻同号下面是“+”号，2个相邻异号下面是“-”号。
+ + _ + _ + + + _ _ _ _ + _ + + + _ _ + + _ _ + _ _ _ +在一般情况下，符号三角形第一行有N个符号，该问题要求对于给定n计算有多少种不同的符号三角形。使其所含的+ — 个数相同。
递归回溯算法模板
void backtrack(int t) //t表示递归深度，即当前扩展节点在解空间树的深度
{
if ( t > n ) output(x); //n控制递归深度，如果算法已经搜索到叶节点，记录输出可行解X
else
{
for(int i = f(n,t) ; i <= g(n,t) ; i++) //在深度t，i从未搜索过得起始编号到终止编号
{
x[t] = h(i); //查看i这个点的值是否满足题目的要求
if( constraint(t) && bound(t))
backtrack(t+1)
//constraint（t）为true表示在当前扩展节点处x[1:t]的取值满足问题的约束条件；
//bound(t)为true表示当前扩展节点取值没有使目标函数越界；
//为true表示还需要进一步的搜索子树，否则减去子树。
}
}
}8.概率算法思想
概率算法依照概率统计的思路来求解问题，往往不能得到问题的精确解，但却在数值计算领域得到了广泛的应用。因为很多数学问题，往往没有或者很难计算解析解，这时便需要通过数值计算来求解近似值。
基本思想
通过概率统计来求解问题，但是不能求解精准答案，概率算法大致分为如下4中形式：
- 数值概率算法；
- 蒙特卡洛(Monte Carlo)算法；
- 拉斯维加斯(Las Vegas)算法；
- 舍伍德(Sherwood)算法；
简而言之，与确定性算法相比，若冒险，可能做得更好！这就是概率算法的魅力
基本步骤
- 将问题转化为相应的几何图形S，S的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1的面积
- 然后，向几何图形中随机撒点.
- 统计几何图形中S中和S1中的点数，根据S的面积和S1面积的关系以及各图形中的点数来计算得到结果.
- 判断上述结果是否在需要的精度之内，如果未达到精度则进行执行步骤2.如果达到精度，则输出近似结果.
经典例子
- 蒙特卡罗计算圆周率
9.双指针思想
一般暴力的做法的复杂度往往达到O(n^2）复杂度，双指针算法是运用题目内部的具体逻辑将上述算法的复杂度降到O(n)，是一种常用的有效的降低算法复杂度的算法思想
基本思想
双指针其实是利用数组（或者求解问题）的有序特性，在遍历的过程中使用两个相同方向或者相反方向的指针进行扫描，从而达到目的的一种算法。（注：这里的指针并非专指c语言中的指针，表达的含义是下标、索引值或者是可进行迭代的对象等）
算法模板
我们常见的一般的二重循环如下：
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
}
}而双指针算法可以将上面的二重循环优化成这样（模板不唯一）：
for(int i = 0, j = 0; i < n; i ++) {
while(j < i && check(i,j)) {
j++;
}
}虽然看上去仍然是循环套循环，但是实际上是一个O(n)的时间复杂度。因为每一个指针在所有循环里面总共移动的次数是不超过n的，那么两个指针总共移动的次数不超过2n次。
双指针算法的分类
基于不同双指针算法的适用情况，我将其分为3类：
- 快慢双指针。用于解决链表问题，两指针一快一慢从链表头节点head扫描至链表末节点（从数据结构上也很容易理解，因为链表结构只能顺藤摸瓜，只能从头扫到尾，木有其他扫描方式）
- 首尾双指针，特点是【夹逼】。用于解决顺序表问题，两个指针一个指头、一个指尾，向中间夹逼，两指针相遇时结束，此时刚好扫描整个顺序表一次
- 蠕动双指针。也就是滑动窗口，特点是【一伸一缩】。用于解决顺序表问题，两个指针都从顺序表头部出发，一个指针做蠕虫头，另一指针做蠕虫尾，一伸一缩蠕动前进，直到蠕虫抵达顺序表末尾。我们都知道蚯蚓，蚯蚓怎么蠕动的呢？当蚯蚓前进时，身体后部的刚毛钉入土里，使后部不能移动，这时身体就向前伸长；接着身体前部的刚毛钉入土里，使前部不能移动，这时向前缩短。就这样，蚯蚓一伸一缩完成向前移动。那么我们想象一条蚯蚓爬过一个顺序表（如一个数组），这就是蠕动双指针的工作模式
经典例子
- 有序数组的两数和：在有序数组中找出两个数，使它们的和为 target。
- 回文字符串：可以删除一个字符，判断是否能构成回文字符串。
- 判断链表是否存在环：使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。
