一、数据结构与算法总览
数据结构
一维
数组array 链表link list 高级（栈stack 队列queue 双端队列deque 集合set 映射map、hash ）
二维
树tree 图graph 高级（二叉搜索树 binary search tree/red-black tree ,AVL）堆、并查集disjoint set 、字典树Trie
特殊
位运算bitwise 布联系吧过滤器bloomFilter
LRU Cache
算法
- if..else , switch -> branch
- while loop , for –> lteration
- 递归 Recursion
- 搜索：深度优先DFS 广度优先BFS
- 动态规划Dynamic Programming
- 二分查找 Binary Search
- 贪心 Greedy
- 数学 Math 几何 Geometry
切题四步法
- 反复看题 clarification
- 想所有可能的解法 Possible Solutions 时间空间复杂度
- 多写coding
- 测试样例多写下 test cases
五毒神掌 五遍刷题法
- 刷题第一遍
- 5分钟 读题+思考 最多15分钟
- 直接看解法 ：多解法 再比较复杂度
- 背记 默写
- 刷题第二遍
- 马上自己写
- 多解法比较 体会 优化！
- 刷题第三遍
- 过了一天后，重复做题
- 不同的解法熟练程度 并进行专项练习
- 刷题第四遍
- 过了一周后，重复做题，国际站看大神解题
- 刷题第五遍
- 面试前一周恢复性训练
二、复杂度
时间复杂度
O(1) 常数复杂度 若执行了3次还是常数，依然是O(1)
O(logn) 对数复杂度
O(n) 线性时间复杂度 for循环 并列循环
O(n^2) 平方 嵌套for循环
O(n^3) 立方 3层嵌套for循环
O(2^n) 指数 斐波拉数列 k的n次方 k是常数
O(n!) 阶乘
主定理算递归复杂度
二分查找
二分树遍历
二维距阵进行二分查找
归并排序
空间复杂度
数组长度
递归的深度
三、数组、链表、跳表
链表 数组
prepend O(1) O(1)
append O(1) O(1)
lookup O(n) O(1)
insert O(1) O(n)
delete O(1) O(n)
跳表：只能用于有序的情况，对标的平衡数和二分查找。优势原理简单容易实现，方便扩展，效率更高。
Redis.LRU缓存机制