# 【精通一个领域的三步】
* 来自书籍：《异类：不一样的成功启示录》
 
## 1、Chunk it up 切碎知识点
## 2、Deliberate Practicing 刻意练习
* 过遍数
* 练习弱点、缺陷的地方
* 不舒服、枯燥、不爽
 
## 3、Feedback 反馈
###  主动型反馈（自己去找）
* 高手代码（GitHub，LeetCode）
* 第一视角直播
 
### 被动型反馈（高手指点）
* code review
* 教练看你打，给你反馈
 
 
# 【做题思路】
## Clarification
* 多看几次题目，跟面试官反复沟通，确保自己理解没有问题
 
## Possible solutions
* 想所有可能的解法，比较一下时间空间复杂度，找出最优的解法（一般是时间最快的）
 
## Coding
* 开始写代码
 
## Test cases
* 写测试样例，进行测试
 
# 【刷题方法】
* 切忌只做一遍
 
## 刷题第一遍
* 先花5分钟读题、思考（最多花10分钟）
* 5分钟没有思路，直接看解法，并且比较不同解法的优劣性
* 背诵和默写好的解法
 
## 刷题第二遍
* 马上在LeedCode自己独立去写
* 多种解法比较体会， 进行优化（效果要领先90%的人）
 
## 刷题第三遍
* 过了24小时后，再重复做题
* 不同解法的熟练程度，进行专项练习
 
## 刷题第四遍
* 过了一周后，练习相同的题目
 
## 刷题第五遍
* 面试前一周左右恢复性训练
 
 
# 【数据结构】
## 一维数据结构
* 基础：数组array (string) 链表 linked list
 
* 高级：栈stack，队列queue，双端队列deque，集合set，映射map（hash or map）
 
## 二维数据结构
* 基础：树tree，图Graph
 
* 高级：二叉搜索树binary search tree（red-black tree, AVL）,堆heap，并查集disjoint set，字典树Trie
 
## 特殊数据结构
* 位运算Bitwise，布鲁过滤器Bloom Filter
* LRU Cache
 
# 【算法】
* 核心是寻找重复单元。
 
## 1、跳转（基石）
If-else, switch -->branch
 
## 2、循环（基石）
for while loop -->Iteration
 
## 3、递归（基石）
Recursion，（Divide & Conquer，Backtrace）
 
## 4、搜索Search
深度优先Depth first search、广度优先Breadth first search
 
## 5、动态规划
Dynamic Programming
 
## 6、二分查找
Binary search
 
## 7、贪心
Greedy
 
## 8、数学Math和几何Geometry
 
 
# 时间复杂度
* 用来表示程序执行的次数
 
## O(1)
* Constant Complexity 常数复杂度
 
## O(log n)
* Logarithmic Complexity 对数复杂度
 
## O(n)
* Linear Complexity 线性时间复杂度
 
## O(n^2)
* N square Complexity 平方
 
## O(n^3)
* N square Complexity 平方
 
## O(2^n)
* Exponential Growth 指数
 
## O(n!)
* Factorial 阶乘
 
## 主定理
* 通过主定理可以数学推导出时间复杂度。
* 二分查找：O(log n)
* 二叉树遍历：O(n)
* 对有序二位矩阵进行二分查找：O(n)
* 归并排序 ：O(n * log n)
 
# 数组 Array
* 操作系统开辟一块连续的内存，可以通过数组的下标对数组进行访问，优点读O(1)  取方便，但是中间节点增删O(n)麻烦，而且每次数组增加长度都是new一个，首尾节点增删是O(1)。
 
# 链表 Linked List
* 增删都是O(1)，查找是O(n)
 
# 跳表 Skip List
* 通过升维和空间换时间的思想模式，对链表进行优化。为链表数据增加索引。 查询为O(log n)
* 工程应用：LRU Cache 和 Redis
 
# 栈 Stack
* 先入后出
* 添加删除是O(1)，查询是O(n )原因是数据是无序的
 
# 队列 Queue
* 先入先出
* 添加删除是O(1)，查询是O(n )原因是数据是无序的
 
## 双端队列Deque： Double-End Queue(常用)
* 首和尾都可以进行增删
 
## 优先队列 Priority Queue
* 插入是O(1)
* 取出是O(log n)，按照元素优先级取出
* 底层具体实现的数据结构较为多样和复杂：heap，bst（二叉搜索树），treap
 
# 哈希表 Hash table
* 根据关键码值直接访问的数据结构，把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫散列函数，存放记录的数组叫哈希表。
如果发生哈希碰撞，会进行拉链式解决，在发生碰撞的数据里采用链表结构，这种情况下查询不是O(1)的，因为会遍历碰撞的数据。哈希函数选的不好或者哈希表的大小太小会导致发生大量哈希碰撞，此时，数据结构会退化到链表结构。
 
# 树 Tree
* 跟图的最大区别是没有形成环
* 前序遍历：根左右
* 中序遍历：左根右
* 后序遍历：左右根
 
# 图 Graph
* 跟树的最大区别是形成环
 
# 二叉搜索树 Binary Search Tree
* 是指一颗空树或者满足下列性质的二叉树：
1. 左子树上的**所有节点**的值均小于根节点
2. 右子树上的**所有节点**的值均大于根节点
3. 以此类推，左右子树也分别为二叉查找树。
 
* 插入和查询、删除是O(log n)
 
# 递归
* 判断结束条件
* 处理当前层逻辑
* 调用函数下探一层
* 处理返回结果
 
# 分治和回溯
* 本质上都是递归，都是在找重复性
* 分治是在递归的基础上加上拆分成子问题，处理中间结果
* 回溯就是不断的在每一层去试，发现不行再去掉。
 
 
# 搜索
### DFS 深度优先
* 递归 或者用 栈
### BFS 深度优先
* 用实现队列
 
# 贪心 Greedy
* 找每一步中最优的，来确定最终最优解。这种算法比较绝对，并不适合所有情况。
* 贪心跟动态规划的区别在于，动态规划会保存以前的结果可以回退，而贪心不行。
* 贪心比较高效，得到的结果不是很精确，但是会比较解决最优解。