作业：整理自己的数据结构和脑图

数据结构

• 排序
  • O（n^2)
    • 冒泡排序
    • 插入排序
    • 选择排序
  • O（nlogn)
    • 快速排序
    • 归并排序
  • O（n)
    • 桶排序
    • 计数排序
    • 基数排序
• 非受线性结构
  • 顺序结构
    • 数组
      • 支持 O（1）的随机访问
      • 平均为 O（n）的插入和删除
      • 警惕越界错误，导致 Stack Over Flow
  • 链式结构
    • 单链表
      • 不支持随机访问，需要遍历去访问节点
      • 插入和删除只需要移动指针，时间复杂度为 O（1）
      • 每个节点需要额外的存储指针，需要的内存比数据大
    • 双链表
      • 再单链表的基础上，除头节点外，每个节点多了一个存放前驱节点内存地址的指针
    • 循环链表
      • 尾节点指针指向头结点
    • 静态链表
      • 借助数组，伴随指向后继节点的指针
• 受限线性表
  • 栈
    • 顺序和链表都可以实现，先进后出
    • 实际应用
      • 浏览器的前进与后退
      • 括号匹配
      • 表达式运算
  • 堆
    • 大顶堆
    • 小顶堆
    • 实际应用
      • 找第 K 大元素
  • 队列
    • 普通队列
      顺序和链表都可以实现，先进先出
    • 双边队列
      入口和出口都可以进队和出队
    • 优先级队列
      根据优先级来出队
    • 实际应用
      LRU Cache
• 树与二叉树
  • 特点
    • 顺序和链式都可以实现
    • 遍历方式
      • 广度优先搜索
      • 深度优先搜索
        • 前序遍历
        • 中序遍历
        • 后续遍历
        • 不使用递归的方式完成
  • 二叉树
    • 定义
    • 特点
  • 完全二叉树
  • 满二叉树
  • 二叉搜索树
  • 平衡二叉树
    • 红黑树

算法

• 复杂度
  • 时间复杂度
    • O（1）常数复杂度，最佳，比如 Hash 表，缓存等
    • O（log n）仅次与常数复杂度，如二分查找、二叉搜索树等
    • O（n）线性复杂度，如大多数遍历操作
    • O（n^2）双重 for 循环
    • O（2^n）递归的时间复杂度
  • 空间复杂度
    • O（1）原地操作
    • O（n）开辟线性辅助空间
• 数组
  • 连续空间
  • 查找快、插入/删除 慢
• 链表
  • 离散空间
  • 查找慢，插入/删除节点快
• 栈
  • 先进后出
• 队列
  • 先进先出
• 映射
• 集合
• 并查集
  • 站队问题
  • 初始化
  • 查询，合并
  • 路径压缩
• 树
  • 二叉树
    • 遍历
      • DFS
      • BFS
    • 二叉搜索树
    • 平衡二叉树
      • AVL 树
      • 红黑树
    • 剪枝
  • 字典树
• 递归，分治
  • 盗梦空间
  • 终止空间
  • 本层处理
  • Drill Down
  • 本层状态清理
• 二分查找
  • 有序
  • 有界
  • 能够通过索引随机访问
• 贪心算法
  • 判断能不能贪心
  • 弱化版的动态规划
• 动态规划
  • 简单版本是递归加缓存
  • 高版本是地推公式
  • 状态的定义
    • 有的场景需要套用模板
  • 最优子结构
  • 状态转移方程
• 位运算
  • 需要记忆一些常见的运算方式
• 布隆过滤器
  • 判断不存在 100% 准确
  • 判断存在误差
  • 利用 Hash 函数将待判断 Key 对应的多个位上
• LRU
  • HashTable + 双向链表
  • get 和 set 都是 O（1）的复杂度