感想
历经两个月的时间，将算法知识重新梳理完成，整个过程挺累的，每天只能晚上或者周六周日梳理一部分，虽然占用了大量的休息时间，不过整个过程很充实，而且也重新学到了不少东西。
其实以前自己的算法还是挺不错的，只不过工作之后忙于业务，把算法方面的东西给放下了，当然了，不止算法，很多其他的知识也没再去整理。
前些日子看完左耳听风后，有很多感触，计算机本就是我所热爱的工作，像这种基础性的知识一定要经常复习。而且经过这次整理，我发现两点
- 系统性整理知识点受益颇深
- 至少每周都要找时间刷一下算法题，这能锻炼自己的思维，保持自己的灵敏
算法篇的学习有点像武功，口诀和招式是分开的，口诀就是这些文章，讲述了各种算法的思路，招式就是https://github.com/shidawuhen/asap/tree/master/controller/algorithm 这些算法题，需要合在一起看，效果才会更好。大家也可以关注博客https://shidawuhen.github.io/%E7%AE%97%E6%B3%95/，文章里的算法题会不定时更新。
完成的所有章节为：
研究这些章节和具体的算法题，会发现算法题一般分为两个大类，一类是正好符合这些核心算法，比较容易进行解题，另一类是需要好多小的技巧和看到对应的突破点，然后再回归到这些核心算法。而且我们也能发现，同样的算法题可以用多种算法进行解答，如果有能力实现多种算法解同一道题，也是很有成就感的事情。
下面简单回顾一下这些算法，如果大家时间不够，可以只看这篇文章，希望对大家有帮助
算法回顾
蛮力法
蛮力法思路很简单，但是性能一般不高。但是很多题都会用到蛮力法来解决，这些问题一般都需要用到技巧。蛮力法也不需要啥套路，蛮干就行。这里推荐几道题
- 剑指 Offer 53 - II. 0～n-1中缺失的数字 - 简单 代码 蛮力法最基础的练习
- 19. 删除链表的倒数第N个节点 - 中等 代码 这道题也是使用蛮力法，不过需要使用到技巧，这种技巧往往让人拍手称赞
- 912. 排序数组- 中等 代码 选择排序，必会知识
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 中等 代码 冒泡排序，必会知识
- 686. 重复叠加字符串匹配 - 简单 代码 KMP，经典算法
分治法
分治法将一个难以直接解决的大问题划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。其设计思想为
- 大问题划分成一些规模较小的子问题，以便各个击破，分而治之
- 最好使子问题的规模大小相等
- 最好使各子问题之间相互独立。如果子问题不独立，分治法需要重复的求解公共的子问题，此时虽然也可以用分治法，但一般用动态规划法较好
一般的求解过程如下
- 划分：即分治，划分为小问题
- 求解子问题：一般用递归的方法求解各个子问题，有时递归也可以用循环来实现
- 合并：把各个子问题的解合并起来
这里推荐几道题
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 中等 代码 归并排序，必会知识
- 面试题 16.16. 部分排序 - 中等 代码 快速排序，必会知识
- 53. 最大子序和 - 简单 代码 可以练习一下子问题不完全独立的情况
减治法
分治法是把一个大问题划分为若干个子问题，分别求解各个子问题，然后再把子问题的解进行合并得到原问题的解。减治法同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。减治法在将原问题分解为若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系，这种关系通常表现为：
（1）原问题的解只存在于其中一个较小规模的子问题中；
（2）原问题的解与其中一个较小规模的解之间存在某种对应关系
这里推荐几道题
- 剑指 Offer 53 - II. 0～n-1中缺失的数字 - 简单 代码 二分查找，必会知识
- 面试题 17.14. 最小K个数 - 中等 代码 堆排序，必会知识
动态规划法
动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分为3个阶段：
1）分段：将原问题分解为若干个相互重叠的子问题
2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式
3）求解：利用递推式自底向上计算，实现动态规划过程
这三个阶段其实是有套路的
- 首先反证法证明满足最优性原理
推导出动态规划函数 - 这是最重要的一点
- 动态规划函数在推导前要确认该函数满足题目的解
- 可以画图来帮助做动态规划函数的推导
- 记录中间过程 - 这是核心中的核心
这里推荐几道题
- 面试题 08.01. 三步问题 - 简单 代码 最简单的动态规划题目，可以帮助大家掌握动态规划的思想和套路
- 1143. 最长公共子序列 - 中等 代码 标准动态规划问题，必做
贪心法
使用贪心法的前提需要证明贪心法能获得最优解，否则不要用。
用贪心法求解的问题一般有两个最重要的性质：最优子结构性质和贪心选择性质。
1）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理，问题的最优子结构性质是该问题可以用动态规划法或贪心法求解的关键特征。
2）贪心选择性质：所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到，贪心法通常以自顶向下的方式作出一系列的贪心选择。确定是否有贪心选择性质
- 通常先考察问题的一个整体最优解，并证明可修改这个最优解，使其从贪心选择开始
- 作出贪心选择后，原问题简化为规模较小的类似子问题
- 用数学归纳法证明，通过每一步贪心选择，最终可得到问题的整体最优解
使用贪心法也是有套路的
- 证明可以从贪心选择开始
- 证明使用贪心选择后，问题简化为规模较小类似子问题
- 最终使用归纳法证明能产生最优解
这里推荐几道题
- 1024. 视频拼接 - 中等 代码 使用贪心法的经典问题
- 1383. 最大的团队表现值 - 困难 代码 提升一下难度的练习题
回溯法
回溯法其实就是深度优先遍历，整体比较简单，能够用来计算很多的问题，在计算过程中，如果有更多的剪枝条件，可能进一步加快计算出结果的速度。
回溯法解题一般有两种方式，递归和迭代。比较推荐递归的方式，相对于迭代，思路上更加容易理解。
这里推荐几道题
- 面试题 08.12. 八皇后 - 困难 代码 经典问题
- 257. 二叉树的所有路径 - 简单 代码 比较简单的练习题
分支限界法
回溯法是深度优先策略遍历问题的解空间树。分支限界法按广度优先策略遍历问题的解空间树，在遍历过程中对已经处理的每一个节点根据衔接函数估算目标函数的可能取值，从中选取使目标函数取得极值(极大或极小)的节点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。
广度优先策略其实比深度优先策略略复杂一些，因为需要找到合适的限界函数，同时对于计算出的中间值，需要能够快速的获取到最大/最小的中间值，另外还需要记录好经过的路径。好处在于广度优先策略也是有套路的
- 根据题目确认解的上下界
- 如何确定合适的限界函数
分支限界法在遍历过程中根据限界函数估算某节点的目标函数的可能取值，一定要设计出好的限界函数。
- 如何组织待处理节点表（组织中间结果）
表PT可以采用堆的形式，也可以采用优先队列的形式
如何确定最优解中的各个分量
- 对每个扩展节点保存根节点到该节点的路径
- 在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子节点不断回溯到根节点，以确定最优解中的各个分量。
这里推荐几道题
- 107. 二叉树的层次遍历 II - 简单 代码 简单的广度优先遍历，不需要限界函数，维护中间结果，可以帮助掌握广度优先策略
- 207. 课程表 - 中等 代码 也算维护了简单的中间结果
总结
到这里，算法篇就结束了，后面还是会不断练习一些算法题，加深自己对这些算法的理解，同时也会学习一些新的算法技巧。
今后可能再做一个 设计模式 系列，不过目前欠自己的一些文章比较多，会先补一下别的内容。
希望这个算法系列能够帮助到大家。
最后
大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）
我的个人博客为：https://shidawuhen.github.io/
往期文章回顾：
算法
技术
- 微服务之服务框架和注册中心
- Beego框架使用
- 浅谈微服务
- TCP性能优化
- 限流实现1
- Redis实现分布式锁
- Golang源码BUG追查
- 事务原子性、一致性、持久性的实现原理
- CDN请求过程详解
- 记博客服务被压垮的历程
- 常用缓存技巧
- 如何高效对接第三方支付
- Gin框架简洁版
- InnoDB锁与事务简析
读书笔记
思考
