- 数据结构和算法
- 数据结构
- 集合
- 哈希表
- 模型
- 基本操作
- 添加
- 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
- 函数调用
- 括号匹配
- 单调栈 (表示优先级)
- 表达式求值
- 记录轨迹
- 浏览器的前进后退功能
- 深度优先搜索
- 回溯
- LIFO
- 模型
- 队列
- 模型
- 操作受限的线性表,在一端添加,在另一端删除
- FIFO
- 操作受限的线性表,在一端添加,在另一端删除
- 基本操作
- 入队列
- 出队列
- 查看队头元素
- 判空
- 判满
- 实现
- 动态数组 (循环数组)
- 链表
- 应用
- 缓冲区
- 缓存
- 公平性
- 广度优先搜索
- 三度好友
- 模型
- 树
- BST
- 模型
- key值能进行比较:L < D < R
- 左子树也是一棵二叉搜素树
- 右子树也是一棵二叉搜素树
- 基本操作
- 添加
- 删除
- 查找
- 遍历
- 深度优先遍历
- 先序遍历
- D L R
- 中序遍历
- L D R
- 后序遍历
- L R D
- 先序遍历
- 广度优先遍历
- 层次遍历
- 深度优先遍历
- 实现
- 作用
- 存储动态的有序数据
- 应用
- C++: map, set
- Java: TreeMap, TreeSet
- epoll
- 模型
- BST
- 图
- 集合
- 算法
- 排序
- 选择排序
- 时间:O(n^2)
- 对数据不敏感
- 比较:(n-1) + (n-2) + … + 1
- 交换:n-1
- 对数据不敏感
- 空间
- O(1)
- 稳定性
- 不稳定
- 时间:O(n^2)
- 冒泡排序
- 时间
- 最好情况: 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(n)
- 空间
- 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(n)
- 空间
- O(1)
- 稳定性
- 稳定
- 时间
- 希尔排序
- 类比:多人轮流抓牌
- 时间
- 和gap序列相关,一般来说小于 O(n^2)
- 空间
- O(1)
- 稳定性
- 不稳定
- 归并排序
- 时间
- 对数据不敏感:O(nlogn)
- 空间
- O(n) + O(logn) = O(n)
- 稳定性
- 稳定
- 时间
- 快速排序
- 时间
- 最好情况:O(nlogn)
- 每次分区,基准值都位于中间
- 最坏情况:O(n^2)
- 每次分区,基准值都位于两端
- 平均情况:O(nlogn)
- 最好情况:O(nlogn)
- 空间
- O(log n)
- 稳定性
- 不稳定
- 改进方法
- 基准值选取
- 随机选取
- 选择3个或5个元素的中位数
- 如果相等的元素比较多
- 三向分区
- 当区间元素比较少时,比如小于64
- 插入排序
- …
- 基准值选取
- 时间
- 堆排序
- 时间
- 对数据不敏感:O(nlogn)
- 空间
- O(1)
- 稳定性
- 不稳定
- 时间
- 选择排序
- 二分查找
- 前提
- 随机访问元素
- 底层数据结构是数组
- 有序
- 通过一次比较,可以丢掉一半区间
- 随机访问元素
- 实现
- 递归 (了解)
- 循环 (必须掌握)
- 二分查找的变种
- 查找第一个等于key值的元素
- 查找最后一个等于key值的元素
- 查找第一个大于等于key值的元素
- 查找最后一个小于key值的元素
- 前提
- 排序
- 数据结构