复杂度

时间复杂度

     - O(1)常数复杂度 最佳，Hash表 缓存
     - O(logn) 第二佳 二分查找 二叉搜索树
     - O(n) 线性复杂度 一般的遍历
     - O(n^2) 双重for循环
     - O(2^n) 递归

空间复杂度

     - O(1) 原地操作
     - O(n) 开辟辅助空间

数组

• 连续空间
• 查找快 插入删除慢

链表

• 离散空间
• 查找慢 插入删除快

栈

• 先进后出

队列

• 先进先出

映射

• K/V键值对 K不重复

集合

• Key不重复

并查集

• 站队问题
• 初始化
• 查询 合并
• 路径压缩

树

二叉树

  - 遍历
     - DFS
     - BFS
  - 二叉搜索树
  - 平衡二叉树
     - AVL树
     - 红黑树
  - 剪枝

字典树

  - 空间换时间

图

• 遍历时需记录已访问的结点

递归、分治

• 盗梦空间
• 终止状态
• 本层处理
• Drill Down
• 本层状态清除

二分查找

• 有序
• 有界
• 随机访问

贪心算法

• 判断能否贪心
• 弱化版动态规划

动态规划

• 简单版
  • 递归加缓存
• 高级版
  • 递推公式
• 状态的定义
  • 有些有模版
• 最优子结构
• 状态转移方程

位运算

• 需要记忆一些常见的位运算公式

布隆过滤器

• 判断100%不存在
• 判断存在时可能有误差
• 利益Hash函数将待判断的Key对应到多个位上

LRU

• HashTable+双向链表
• get和set都是O(1)