算法训练营毕业总结

1.刻意练习–过遍数

学习要点 基本功是区别业余和职业选手的根本。深厚功底来自于 — 过遍数

最大的误区：只做一遍

五毒神掌

刻意练习 - 练习缺陷弱点地方、不舒服、枯燥

反馈 - 看题解、看国际版的高票回答

切题四件套

clarification

possible solutions

compare（time/space）

optimal（学习最优解加强）

coding（多写）

test cases

2.五遍刷题法（五毒神掌）：

练习缺点、弱点地方，不舒服、枯燥、不爽—就是在进步；

①刷题第一遍

5-15分钟：读题+思考 直接看解法：注意看多解法、比较解法优劣 背诵、默写好的解法。

②刷题第二遍

马上自己写 -->leetcode提交 多种解法，体会优劣；

③刷题第三遍

过了一天后在重复做题

④刷题第四遍

过了一周后：反复回来练习相同题目

⑤刷题第五遍

面试前一周准备

3、递归 Recursion

递归 – 循环

通过函数体来进行循环

四个条件：

递归终止条件 处理当前层逻辑 下探到下一层 清理当前层

思维要求

不要再进行人肉递归（最大误区）

找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）

数学归纳法

分治思维：

递归终止条件 拆分子问题 调子问题的递归函数 合并结果，有可能要恢复当前层的状态

4、动态规划

动态规划和递归或者分治，没有根本上的区别（关键看有无最优子结构）

共性：找到重复子问题

差异性：最优子结构，中途可以淘汰次优解

动态规划关键点：

最优子结构 opt[n] = best_of(opt [n-1], opt[n-2],....)（子问题）

储存中间状态:opt[i] (状态定义）

递归公式（状态转移方程或者DP方程）

高阶dp

状态拥有更多维度 状态方程更加复杂

5、字典树，Trie

字典树，即Trie树，又称单词查找树或键树，是一种数据结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点在于：最大限度的减少无谓的字符串比较，查找效率比哈希表高。

基本性质：

节点本身不存完整单词；

从根节点到某一节点路径上经过的字符链接起来，为该节点的字符串；

每个节点的所有子节点路径代表字符都不相同。

核心思想 Trie树的核心思想就是空间换时间

利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的

6、并查集

适用场景：组团、配对问题

基本操作：

makeset(s)：建立一个新的并查集，其中包括s个单位元素集合；

unionset(s):把元素x和y所在的元素集合合并，要求x和y所在的集合不相交，如果相交则不合并；

find(x):找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将他们各自的代表比较一下即可；

算法训练营结束了，但是算法的学习之路才刚刚开始，加油！