算法训练营学习笔记（一）
目录
摘要
算法训练营学习笔记（一）。
01 数据结构与算法总览
如何有效学习数据结构与算法
思想来自于《异类》
Chunk It Up （切碎知识点）
纲领
-
庖丁解牛
-
脉络相连
- 人脑不适合理解和记忆孤立的知识。
数据结构
- 一维数据结构：
- 基础型：
- 数组（Array）
- 链表（Linked List）
- 高级型：
- 栈（Stack）
- 队列（Queue）
- 双端队列（Deque）
- 集合（Set）
- 映射（Map / HashMap）
- 基础型：
- 二维数据结构（一维结构泛化而来）
- 基础型：
- 树（Tree）
- 图（Graph）
- 高级型：（在树的基础上加约定判断与特殊条件）
- 二叉搜索树（Binary Search Tree）、红黑树、AVL
- 堆（Heap）
- 并查集（Disjoint Set）
- 字典树（Trie）
- 基础型：
- 特殊数据结构
- 位运算（Bitwise）
- 布隆过滤器（Bloom Filter）
- LRU Cache
算法（寻找重复部分）
- 分支（Branch）
- If-Else
- Switch
- 循环（Loop）
- For Loop
- While Loop
- 递归（Recursion）
- Divide & Conquer
- Backtrace
- 搜索（Search）
- 深度优先搜索（Depth Fist Search）
- 广度优先搜索（Breath First Search）
- 启发式搜索（A*）
- 动态规划（Dynamic Programming）
- 二分查找（Binary Search）
- 贪心算法（Greedy）
- 数学（Mathematics）、几何（Geometry）
Deliberate Practice （刻意练习）
职业化运动
- 基本功是区别业余与职业选手的最大区别。
- 基础动作的分解与反复练习。
刻意练习：
- 过遍数（五遍刷题法——五毒神掌）
- 练习缺陷、弱点地方。
Feedback （反馈）
即时反馈
主动反馈（自己去找）
- 高手代码
被动反馈（高手给你指点）
- Code Review
刷题技巧
思考方式（切题四件套）
- Clarification：彻底理解题目。
- Possible Solutions
- 不要用想到的第一种方法去解。
- 先把所有可能的方法过一遍。
- 比较不同方法的时间复杂度与空间复杂度。
- 找出最优解（最快的那个）。
- Coding
- Testing Cases
五毒神掌（五遍刷题法）
- 任何一个题目至少做5遍。
- 第一遍：
- 5-15分钟：读题 + 思考。
- 若无思路，直接看解法。多解法，比较优劣。
- 背诵、默写好的解法。
- 第二遍：
- 马上自己写。
- 提交LeetCode修改。
- 多种解法比较、体会，进而优化。
- 第三遍：
- 24小时后，再重复做题。
- 针对不熟练的地方，专项训练。
- 第四遍：
- 一周后，重复做题。
- 针对不熟练的地方，专项训练。
- 第五遍：面试前，恢复性训练。（时间自己判断）
02 训练准备与复杂度分析
训练环境设置
电脑设置
LeetCode
- 国际站的Discuss
编码技巧
- IDE 的 Top Tips
Code Style
自顶向下的编程方式
来自《Clean Code》
- 报纸方式，最重要的写在最前面。
- 先写空函数完成主干逻辑。
- 再补全实现细节。
时间与空间复杂度
- Big $O$ Notation
时间复杂度
常见复杂度：
- $O(1)$：常数复杂度（Constant Complexity）
- $O(log(n)$：对数复杂度（Logarithmic Complexity）
- $O(n)$：线性复杂度（Linear Complexity）
- $O(n^2)$：平方复杂度（N square Complexity）
- $O(n^3)$：立方复杂度（）
- $O(2^n)$：指数复杂度（Exponential Growth）
- $O(n!)$：阶乘复杂度（Factorial）
分析复杂度
- 不考虑系数，只看最高复杂度运算。
- 习惯性思考自己所写程序的时间与空间复杂度。
- 对自己所写程序的时间与空间复杂度有所了解。
递归的时间复杂度
- 指数级，有大量冗余计算。
- 主定理（Master Theorem）：算出任何一个分治或递归的时间复杂度。
- 二分查找（一维数组中进行） —— $O(log(n)$
- 二叉树遍历（每个节点访问一次且仅访问一次） —— $O(n)$
- 二分查找（排好序的二维矩阵中进行） —— $O(n)$
- 归并排序 —— $O(n \log(n))$