Data structures and algorithms

,
  • 数据结构和算法
    • 数据结构
      • 集合
        • 哈希表
          • 模型
          • 基本操作
            • 添加
              • hashmap_put(map, key, val)
            • 删除
              • hashmap_delete(map, key)
            • 查找
              • hashmap_get(map, key)
            • 遍历
          • 实现
            • 哈希函数
              • 数据的指纹
                • 正向快速
                • 逆向困难
                • 平均分布
                • 哈希冲突的概率小
                • 对数据敏感
              • 散列
                • 正向快速
                • 平均分布
            • 哈希桶
              • 拉链法
              • 开放地址法
                • 线性探测
                • 平方探测
                • 再散列法
          • 应用
            • C++: unordered_map, unordered_set
            • Java: HashMap, HashSet
            • redis
              • 键值数据库
      • 线性结构
        • 动态数组
        • 链表
          • 单向链表
            • 模型
            • 基本操作
              • 增
                • 在某个结点后面添加
              • 删
                • 在某个结点后面删除
              • 查
                • 根据索引查找值
                  • 平均遍历 n/2 个结点
                • 查找与特定值相等的结点
                  • 无序
                  • 有序
                    • 记录上一次查找的位置
              • 遍历
                • 正向遍历
            • 实现
              • C++: forward_list
          • 双向链表
            • 模型
            • 基本操作
              • 增
                • 在某个结点后面添加
                • 在某个结点前面添加
              • 删
                • 在某个结点后面删除
                • 在某个结点前面删除
                • 删除当前结点
              • 查
                • 根据索引查找值
                  • 平均遍历 n/4 个结点
                • 查找与特定值相等的结点
                  • 无序
                  • 有序
                    • 记录上一次查找的位置
              • 遍历
                • 正向遍历
                • 逆向遍历
            • 实现
            • 应用
              • Java: LinkedList
              • C++: list
        • 栈
          • 模型
            • 操作受限的线性表，只能在一端添加或删除
              • LIFO
          • 基本操作
            • 入栈
            • 出栈
            • 查看栈顶元素
            • 判空
          • 实现
            • 动态数组
            • 链表
          • 应用
            • LIFO
              • 函数调用
              • 括号匹配
            • 单调栈 (表示优先级)
              • 表达式求值
            • 记录轨迹
              • 浏览器的前进后退功能
              • 深度优先搜索
              • 回溯
        • 队列
          • 模型
            • 操作受限的线性表，在一端添加，在另一端删除
              • FIFO
          • 基本操作
            • 入队列
            • 出队列
            • 查看队头元素
            • 判空
            • 判满
          • 实现
            • 动态数组 (循环数组)
            • 链表
          • 应用
            • 缓冲区
            • 缓存
              • 公平性
            • 广度优先搜索
              • 三度好友
      • 树
        • BST
          • 模型
            • key值能进行比较：L < D < R
            • 左子树也是一棵二叉搜素树
            • 右子树也是一棵二叉搜素树
          • 基本操作
            • 添加
            • 删除
            • 查找
            • 遍历
              • 深度优先遍历
                • 先序遍历
                  • D L R
                • 中序遍历
                  • L D R
                • 后序遍历
                  • L R D
              • 广度优先遍历
                • 层次遍历
          • 实现
          • 作用
            • 存储动态的有序数据
          • 应用
            • C++: map, set
            • Java: TreeMap, TreeSet
            • epoll
      • 图
    • 算法
      • 排序
        • 选择排序
          • 时间：O(n^2)
            • 对数据不敏感
              • 比较：(n-1) + (n-2) + … + 1
              • 交换：n-1
          • 空间
            • O(1)
          • 稳定性
            • 不稳定
        • 冒泡排序
          • 时间
            • 最好情况: O(n)
              • 原数组有序
                • 比较：n-1
                • 交换：0
            • 平均情况：O(n^2)
              • 比较：大于等于交换的次数，小于等于 n(n-1)/2
              • 交换：等于逆序对 n(n-1) / 4
            • 最坏情况：O(n^2)
              • 原数组逆序
                • 比较：1 + 2 + … + (n-1)
                • 交换：1 + 2 + … + (n-1)
          • 空间
            • O(1)
          • 稳定性
            • 稳定
        • 插入排序
          • 时间
            • 最好情况: O(n)
              • 原数组有序
                • 比较：n-1
                • 交换：0
            • 平均情况：O(n^2)
              • 比较：大于等于交换的次数，小于等于 n(n-1)/2
              • 交换：等于逆序对 n(n-1) / 4
            • 最坏情况：O(n^2)
              • 原数组逆序
                • 比较：1 + 2 + … + (n-1)
                • 交换：1 + 2 + … + (n-1)
          • 空间
            • O(1)
          • 稳定性
            • 稳定
        • 希尔排序
          • 类比：多人轮流抓牌
          • 时间
            • 和gap序列相关，一般来说小于 O(n^2)
          • 空间
            • O(1)
          • 稳定性
            • 不稳定
        • 归并排序
          • 时间
            • 对数据不敏感：O(nlogn)
          • 空间
            • O(n) + O(logn) = O(n)
          • 稳定性
            • 稳定
        • 快速排序
          • 时间
            • 最好情况：O(nlogn)
              • 每次分区，基准值都位于中间
            • 最坏情况：O(n^2)
              • 每次分区，基准值都位于两端
            • 平均情况：O(nlogn)
          • 空间
            • O(log n)
          • 稳定性
            • 不稳定
          • 改进方法
            • 基准值选取
              • 随机选取
              • 选择3个或5个元素的中位数
            • 如果相等的元素比较多
              • 三向分区
            • 当区间元素比较少时，比如小于64
              • 插入排序
            • …
        • 堆排序
          • 时间
            • 对数据不敏感：O(nlogn)
          • 空间
            • O(1)
          • 稳定性
            • 不稳定
      • 二分查找
        • 前提
          • 随机访问元素
            • 底层数据结构是数组
          • 有序
            • 通过一次比较，可以丢掉一半区间
        • 实现
          • 递归 (了解)
          • 循环 (必须掌握)
        • 二分查找的变种
            1. 查找第一个等于key值的元素
            1. 查找最后一个等于key值的元素
            1. 查找第一个大于等于key值的元素
            1. 查找最后一个小于key值的元素