零、前言
分享一篇由读者 @Kevin_涛 写的算法思想文章：在讲解八大算法思想之前我想先简述以下三个问题，以便大家更好的理解算法。1. 什么是算法？
《算法导论》中对算法的定义是：算法就是任何良定义的计算过程。在计算机科学中，算法可以看作是数据传递和处理的顺序、方法和组成方式，如各种排序算法等；在自然中，算法可以看作是太阳东升西落，海水潮汐潮流，月儿阴晴圆缺；在生活中，算法可以看作是妈妈烹饪红烧鸡翅时出现的食谱，先煎，再炒，再小火收汁等步骤（流口水.gif）。2. 算法的重要性？
这篇文章的重点不是强调算法的重要性，所以我就不多做讲解，可以分享 N.Wirth 教授所说的：程序 = 数据结构 算法。3. 算法怎么学？
这一块其实也可以单独拿出来絮叨一番，这里简单的描述就是理论 实践，理论指算法相关的知识（我其实很少分享这块的知识，因为已经有很多伙伴写了不错的文章，在一个我觉得理论知识还是以书本更为规范），实践则主要指刷题（我想大多数学算法的伙伴是以面试为目的，而面试和考试很像，都需要刷题，而枯燥的刷题一个人往往难以坚持，所以我制定了刷题打卡计划，希望帮助更多小伙伴一起坚持，在我看来养成习惯更为重要）这篇文章不仅用图文并貌的形式阐述了常用的八大算法思想，每个算法思想我还分别选取了一个经典案例予以代码分析。本文耗费了我很多心血，希望大家一定要耐心看完（暂时没时间的话记得先「收藏」哦～），如果对大家有帮助恳请「转发」分享给更多朋友，这就是对我原创最大的动力！感谢！一、枚举
首先，最简单的思想，枚举算法。枚举也叫穷举，言下之意便是根据题目的部分条件确定范围，并在次范围内对所有情况逐一穷尽验证，直到找到那个最符合的解。 我们常用的循环遍历，就是用的穷举思想。枚举算法的思想可以用下图来表示。通过实现事先确定好的「可能解」X，然后逐一在 f()计算中进行验证，根据验证结果对「可能解」进行验证。这是一种结果导向型的思想，简单粗暴地试图从最终结果反向分析「可能解」。枚举算法的劣势也很明显。在实际的运行过程中，能够直接通过枚举方法进行求解的问题少之又少。一方面，当「可能解」的筛选条件不清晰，导致「可能解」的数量和范围无法确定时，枚举就失去了意义。另一方面，枚举发挥不了作用的大部分场景都是由于「可能解」的数量过多，无法在有限空间或有限时间内完成所有可能性的验证。不过，枚举思想是最接近人类的思维方式，我们在没有更好的思路时先用枚举算法得出解不失为一种方法，其实在判断优化方法的正确性时往往就是先用枚举法暴力求出解在验证测试用例。另外，想分享一个 Helsgaun 改进 Lin-Kernighan 算法，形成 Lin-Kernighan-Helsgaun 算法（简称 LKH 算法）的故事。Lin-Kernighan 算法，以及之后的改进算法：Lin-Kernighan-Helsgaun 算法：这个改进思路其实并不复杂，简单来讲，就是每次针对某一个解，同时考虑变换 10 条边，生成一个更优解。关键是，10 条边太多了，所以变换 10 条边的方式非常复杂，大概有 148 种可能之多。这些变换方式之间没有明显的规律，至少数学家们没有找到这个规律。也因为如此，没有人知道要如何实现出这个优化。但是，1998 年，计算机科学家 Keld Helsgaun 给数学界带来了一枚重磅炸弹。他实现了这个改进，完成了 LKH 算法！LKH 算法的实际性能飞跃，比大多数人预计得都要好得多。但最吸引人好奇心的是，Helsgaun 到底是如何实现的这个优化？Helsgaun 向研究界公开了他的完整代码，以此揭示他成功的秘诀。答案是：没有秘诀。他在代码里，完整列出了所有 148 种情形，分别讨论了这些可能性。 他为了写出正确的代码，付出了堪比愚公移山的努力。《案例》
今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？
参考代码：（此文仅用个人擅长的 Java 实现，语言可替换，思想最重要！）/**
* 穷举算法思想
* 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？
* 解法：通过题目可以知道，鸡和兔的总数量为0-35只(每个动物都是一个脑袋，这就不用说了吧)，
* 我们可以假设鸡为0，兔子为35，用鸡的个数*2 兔子的个数*4就可以得到总的脚的数量，如果等于94，那么便是答案，
* 如果不等，则鸡的数量 1，兔子数量-1，依次类推，穷举所有情况直到得到答案
*/
public static void enumeratingAlgorithm() {
int head = 35, foot = 94;
int j;
for (int i = 0; i <= 35; i ) {//i代表鸡的数量
j = head - i;//j代表兔子的数量
if (i * 2 j * 4 == foot) {
System.out.printf('鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。', i, j);
return;
}
}
System.out.printf('此题无解！你家鸡和兔子有三只脚的吧？');
}
鸡的个数为[ 23 ]只,兔子的个数为[ 12 ]只。
二、递推
递推思想跟枚举思想一样，都是接近人类思维方式的思想，根据已有的数据和关系，逐步推导而得到结果，通常是根据前面的一些项得到后面的一些项。递推思想用图解来表示可以参见下图。每一次推导的结果可以作为下一次推导的的开始，这似乎跟迭代、递归的思想有点类似，不过递推的范畴要更广一些。递推算法往往需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有着明确的计算公式可以遵循，因此往往可以采用递推算法来实现。《案例》
这个问题癞子13世纪意大利数学家斐波那契的《算盘书》，问题的大意如下：如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子初剩两个月后才可以生小兔子。也就是说，1月份出生，3月份才可以产仔。那么假定一年没有产生兔子死亡事件，问一年后共有多少对兔子？
从上述内容可以看出，从第3个月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式Fn=F(n-1) F(n-2)，这里的n是第n个月，这里初始第1个月的兔子数为F1=1,F2=1。/**
* 递推算法
* 如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子初剩两个月后才可以生小兔子。
* 那么假定一年没有产生兔子死亡事件，问一年后共有多少对兔子？
* 解法：
* 头两个月，兔子都是只有一对，第三个月是2对，第四个月是3对，第五个月是5对。。。
* 由此可以看出。从第三个月开始，每个月的兔子对数，等于前两个月之和。
* 所以第n个月的兔子对数为 fₙ = fₙ₋₂ fₙ₋₁
*
* @param month 月份
*/
public static int recursiveDeduceAlgorithm(int month) {
int f1, f2;
if (month == 1 || month == 2) {
return 1;
}
f1 = recursiveDeduceAlgorithm(month - 1);//递归调用
f2 = recursiveDeduceAlgorithm(month - 2);//递归调用
return f1 f2;//根据fₙ₋₁和fₙ₋₂，推导出fₙ
}
int month = 12;
int num = recursiveDeduceAlgorithm(month);
System.out.println('经过 ' month ' 个月，共有 ' num ' 对兔子。');
三、递归
说完递推，我们接着来说说它的兄弟思想——递归。两者都用一个「递」字，可以看出应该具有一定的相似性。「递」的理解可以是逐次、逐步。在「递推」中，是逐次对问题进行推导直到获得最终解。而在「递归」中，则是逐次回归迭代，直到跳出回归。程序调用自身的编程技巧称为递归（ recursion）。它通常把一个复杂的问题转换为与原问题相似的规模较小的问题来求解。用一句话来形容递归算法的实现，就是在函数或者子过程的内部，直接或间接的调用自己算法。- 间接递归，间接的调用一个方法。比如方法a调用方法b，方法b又调用方法a。
使用递归，可以是代码更简洁清晰，可读性更好。但是在编写递归方法时，要注意使用 if 语句来在某些情况下强制退出递归返回结果。否则，会形成死循环。无法结束，当然也无法得到实际问题的解。递归算法可用下图表示。递归过程可以形象的表示为一种「套娃」过程。《案例》
所谓阶乘，就是从1到指定数之间的所有自然数相乘的结果。n的阶乘为：n! = n * (n-1) * (n-2) * ······ * 2 * 1
/**
* 递归算法思想
* 求阶乘(factorial)问题
* n的阶乘为：n! = n * (n-1) * (n-2) * ······ * 2 * 1
* 解法，每一项都等于前一项-1，结果也等于之前的结果*前一项-1
* 我们这里用int，要注意int的取值范围，不要超过int的上限。
* @param n 求n的阶乘
* @return n的阶乘
*/
public static int recursiveAlgorithm(int n) {
if (n <= 1) {
return 1;
}
return n * recursiveAlgorithm(n - 1);//递归调用
}
int n = 8;
int result = recursiveAlgorithm(n);
System.out.println(n ' 的阶乘为： ' result)
四、分治
我们可以先从现实中的管理思想理解分治算法，一个大公司从最高级层层划分，将子任务分配给不同的字部门，进而将大问题拆分，最底层得出最基本的解后，又一层层向上级汇报，直至大BOSS作出最终解。同理运用在计算机的世界中，分治算法是将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，从而得到最终答案。 例如我们常说的归并排序就是典型的分治思想的应用。分治思想的图解可见下图。通过层层粒度上的划分，将原问题划分为更小的子问题，然后再向上依次得到更高粒度的解。先分解，再求解，再合并。《案例》
参考代码：（为了便于理解未使用库中的源码，自己手写超详细注释！这么用心只想博你一赞🥺）/**
* @description: 归并排序
* 时间复杂度：O(nlogn)
* 空间复杂度：O(n)
* 稳定排序
* 非原地排序
* @author: Kevin
* @createDate: 2020/2/13
* @version: 1.0
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 5, 3, 9};
userMergeSort(arr);
System.out.println('sorted arr:');
for (Integer i:arr) {
System.out.println(i);
}
}
private static void userMergeSort(int[] arr){
if (arr == null || arr.length == 0) {
return;
}
mergeSort(arr,0,arr.length-1);
}
/**
* 将数组 arr[left] --> arr[right] 进行归并排序
* @param arr 要排序的数组
* @param left 左边界
* @param right 右边界
*/
private static void mergeSort(int[] arr,int left,int right){
//终止条件 --> left == right 的时候，就递归到只有一个元素,则不用递归
if (left < right) {
// [分]: 将数组一分为二
int center = (left right)/2;
// int center = (left right)>>1; // 位运算写法
// [治]: 将左边的数组排序(left --> center)
mergeSort(arr,left,center);
// [治]: 将右边的数组排序(center 1 --> right)
mergeSort(arr,center 1,right);
// [合]: 合并两个有序数组
merge(arr, left, center, right);
}
}
/**
* 将 arr[left...center] 和 arr[center 1...right] 两个有序数组合并为一个有序数组
* @param arr
* @param left
* @param center
* @param right
*/
private static void merge(int[] arr, int left, int center, int right) {
//先用一个临时数组把他们合并汇总起来
int[] temp = new int[arr.length];
int i = left,j = center 1;
// 先通过比较将两个有序数组合并为一个有序数组，结果暂存到 temp 数组
for (int k = left;k<=right;k ){
// 如果左边数组 arr[left...center] 中的元素取完[即比较完](i>center)，
// 则直接复制右边数组的元素到辅助数组。右边数组同理
if (i>center) { temp[k] = arr[j ]; }
else if(j>right) { temp[k] = arr[i ]; }
// 合并时，比较两有序数组值，将小的放入辅助数组中
else if(arr[i]<=arr[j]) {temp[k] = arr[i ]; }
else {temp[k] = arr[j ]; }
}
// 再将已经排序好的辅助数组中的值复制到原数组 arr 中
for (int k=left;k<=right;k ){
arr[k] = temp[k];
}
}
}
WOW～ 你已经看完了50%，真的很棒！接下来的50%难度将增大一点点，相信你一定可以看完，并且收获更大！加油 ：）五、动态规划
动态规划是我比较喜欢的一个算法，它就像人生规划，我们当前所做的抉择受到之前状态的影响，我们当下所遇到的问题可能在之前已经有过答案，并且不论过去状态和决策如何，对之前状态而言，当下的决策必须构成最优策略。
动态规划（Dynamic Programming，简称DP）与分治思想相似，都是通过组合子问题的解来求解原问题。如上所述，分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。不同的是，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划对每个子子问题只求解一次，将其解保持在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。动态规划通常用来求解最优化问题（optimization problem）。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优解（最小值或最大值）的解。我们称这样的解为问题的一个最优解（an optimal solution），而不是最优解（the optimal solution），因为可能有多个解都达到最优值。动态规划的思路如下图解。动态规划的开始需要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，如图中节点的 F0 等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。在这个过程中，下一状态的确定往往需要参考之前的状态。因此需要在每一次状态转移的过程中将当前的状态变量进行记录（如下图的备忘录表格中），方便之后的查找。动态规划主要就是用来解决多阶段决策的问题，但是实际问题中往往很难有统一的处理方法，必须结合问题的特点来进行算法的设计相应的 G() 函数，这也是动态规划很难真正掌握的原因。《案例》
有一个可载重量为 W 的背包和 N 件物品，每个物品有重量和价值两个属性。其中第i个物品的重量为weight[i]，价值为value[i]。现在让你用这个背包装物品，最多能装的价值是多少？
这里我们讨论的是0-1背包问题：每类物品最多只能装一次public class Solution {
public static void main(String[] args) {
int W = 4, N = 3;
int[] weight = {2,1,3}, value = {4,2,3};
int maxValue = knapsack(W,N,weight,value);
System.out.println(maxValue); //6
}
/**
* 0-1背包问题
*
* @param W 背包容量
* @param N 物品种类
* @param weight 物品重量
* @param value 物品价值
* @return
*/
public static int knapsack(int W, int N, int[] weight, int[] value) {
// 初始化动态规划数组，「状态」有两个：用二维数组：一维表示可选的物品，二维表示背包的容量
int[][] dp = new int[N 1][W 1];
// 已经有初始值，dp[0][j] = dp[i][0] = 0 （没有物品或者没有背包空间的时候，能装的最大价值就是0）
for (int i = 1; i < N 1; i ) {
for (int j = 1; j < W 1; j ) {
if (j - weight[i - 1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][j] = dp[i - 1][j];
} else {
// 两种选择：不装 或装入背包，择优
// 如果不装第 i 个物品：最大价值为 dp[i-1][j]（dp[i][j] = dp[i-1][j] 0)
// 如果装入第 i 个物品：最大价值为 dp[i][j] = dp[i-1][j- weight[i-1]] value[i-1]
// 因为 i 是从 1 开始的，所有 weight 和 value 的取值是 i-1
// dp[i-1][j- weight[i-1]]：在装第 i 个物品前提下，背包能装的最大价值是多少
// value[i-1]：加上第 i 个物品的价值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] value[i - 1]);
}
}
}
// 容量为W的背包能装入物品的最大价值
return dp[N][W];
}
}
六、贪心
贪心算法（greedy algorithm）也称贪婪算法。在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临着多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀来，可以使用更简单、更高效的贪心算法，它在每一步都作出当时看起来最佳的选择。也就是说，它总是做出局部最优解，寄希望这样的选择能导致全局最优解。下图表示的是求解对多条直线的交点。很显然，下图中的直线是不存在统一交点的，但是可以通过算法求得统一交点的最优解。若是采用贪心算法，那么在进行迭代时，每一次都会选择离此时位置最近的直线进行更新。这样一来，在经过多次迭代后，交点的位置就会在某一片区域无限轮回跳转。而这片区域也就是能求得出的大致的最优解区域。《案例》
活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i，则它在半开时间区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
public class ArrangeActivity {
/**
* 活动时间安排
*/
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int[] end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
List<Integer> results = arrangeActivity(start, end);
for (int i = 0; i < results.size(); i ) {
int index = results.get(i);
System.out.println('开始时间:' start[index] ',结束时间:' end[index]);
}
//开始时间:1,结束时间:4
//开始时间:5,结束时间:7
//开始时间:8,结束时间:11
//开始时间:12,结束时间:14
}
/**
* 活动安排
*
* @param s 开始时间
* @param e 结束时间
* @return
*/
public static List<Integer> arrangeActivity(int[] s, int[] e) {
int total = s.length;
int endFlag = e[0];
List<Integer> results = new ArrayList<>();
results.add(0);
for (int i = 0; i < total; i ) {
if (s[i] > endFlag) {
results.add(i);
endFlag = e[i];
}
}
return results;
}
}
七、回溯
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。如果你玩过迷宫的话，应该很容易理解回溯思想，我们一般是从起点开始探索路径，当走到死路时，便退回重新试探，直至找到一条完整的前进路径。下面用一张图表示回溯算法的思想，假设目的是从最X0到达X4，需要对所有节点进行回溯遍历路径。那么回溯算法的过程则需要在前进的每一步对所有可能的路径进行试探。比方说，X0节点前进的路径有三条，分别是上中下条的X1。回溯过程的开始，先走上面的X1，然后能够到达上面 X2，但是这时是一条死路。那么就需要从X2退回到X1，而此时X1的唯一选择也走不通，所以还需要从X1退回到X0。然后继续试探中间的X1《案例》
给定一个 没有重复 数字的序列，返回其所有可能的全排列。例如: [1,2,3]其全排列为:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i ) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
八、模拟
许多真实场景下，由于问题规模过大，变量过多等因素，很难将具体的问题抽象出来，也就无法针对抽象问题的特征来进行算法的设计。这个时候，模拟思想或许是最佳的解题策略。模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能，可以用语言来模拟那个功能，模拟成功也就相应地表示编程成功。模拟说起来是一种很玄幻的思想，没有具体的实现思路，也没有具体的优化策略。只能说，具体问题具体分析。那如何用图解来表示呢？如下图所示，任意的输入，经过不规则的处理，得出理想的输出。《案例》
用计算机实现一个随机数1到100之间的数字，然后由用户来猜这个数，根据用户的猜测数量分别给出不同的提示
public class GuessNum {
public static void main(String[] args) {
int aimNum = 0, guessNum = 0, guessCount = 0; // 目标数字，猜的数字，猜的次数
int max = 100, min = 1; // 比较数范围
Random rand = new Random();
aimNum = rand.nextInt(100) 1; // 生成[1, 100]的随机数
System.out.printf('aim num: %d\n', aimNum);
do {
System.out.printf('%d < 目标数 < %d, 输入你猜的数字：', min, max);
Scanner scanner = new Scanner(System.in);
guessNum = scanner.nextInt(); //输入你猜的数字
guessCount ; // 统计猜数字的次数
if (guessNum > aimNum) {
System.out.printf('猜大了\n');
max = guessNum; // 刷新最大值
}else if (guessNum < aimNum) {
System.out.printf('猜小了\n');
min = guessNum; // 刷新最小值
}
} while (guessNum != aimNum);
System.out.println('恭喜你～猜对啦！');
System.out.printf('共猜了%d次\n', guessCount);
if (guessCount <= 5){
System.out.println('你也太聪明了吧，这么快就猜出来了！');
}else {
System.out.println('还需改进哦，相信你下次可以更快的！');
}
}
}
九、总结
如果你看到了这里并且理解了以上八大算法思想，一定要夸你根棒！如果没有看懂不也要气馁，用心多看几遍多思考多学习！另外，学会了算法思想并不一定代表刷题就所向披靡，因为有些题目是将很多思想杂糅在一起，只是角度和侧重点不同。以上《案例》也不是只能用一种思想来解答，只是作为代表来体会对应的算法思想。大多数人作为工程师，虽说不需要天天刷题，也不一定需要写算法。但是，工程的很多方面都运用着算法思想，如 “Java8中Hashmap使用红黑树来实现” 、“Redis底层使用LRU来进做淘汰策略”、“大数据领域很多问题都基于TopK”、“JS原型链里使了类似链表的成环检测”、“MySql为什么索引要用B 树”、“Oracle里的开窗函数如何实现”、“TCP协议的滑动窗口如何控制流量” 等等等等。在我看来，算法不仅仅是对问题的解决，更重要的是对思维的锻炼。最后的最后，希望大家帮忙「点赞」、「在看」、「转发」三连支持～ 这是我原创的最大动力！
