学习数据结构与算法
从 230903 开始，做 POTD 时，无法在 40 分钟内 AC 的一律 ❌，禁止任何留恋。
文件夹说明：
- lecture 内容来自 算法老师左神的 B 站视频。
- POTD 内容来自 geeksforgeeks 的 Problem Of The Day。确保每天更新
- AcWing 暂时只记录周赛题目。
- LeeCode 暂不确定。
TODO：
- [ ] 整理仓库。仓库现已变得臃肿了，笔记中的某些内容已经变得过于啰嗦。
- [ ] 改写可以那些使用递归实现的算法
- [ ] 数论
学习技巧：
- 写算法时，永远记得考虑边界问题
- 人的优势在于使用工具。不要认为只靠想就做出一道算法题有多厉害，真正厉害的应该是能画出来，理清逻辑，并且能给别人讲明白。所以要多画图！
基础班内容
lecture01
- 时间复杂度
- 选择排序、冒泡排序
- 异或运算
- 交换两个数
- 求一个出现奇数次的数字
- 求两个出现奇数次的数字
- 二分法
- 在有序数组中查找某数的位置
- 在有序数组中查找最左侧/最右侧的位置
- 求取局部最小值/最大值
- 对数器
- 插入排序
lecture02
- 递归
- master 公式计算时间复杂度
- 归并排序
- 小和问题
- 快速排序
- 二项划分
- 三项划分
lecture03
- 数组实现完全二叉树
- 堆：大根堆和小根堆（优先级队列）
- heapify
- heapInsert
- 堆存储中位数
- 堆排序
- 完全二叉树转换为大根堆
- 堆扩容
- 比较器
- 非比较排序（桶排序）
- 计数排序
- 基数排序
- 基数排序优化
lecture04
- 排序算法总结（时间复杂度、稳定性）
- 哈希表（map, set）、有序表
- 链表
- 反转链表
- 打印有序链表公共部分
- 快慢指针
- 单链表回文
- 单链表划分
- 复制含有随机指针节点的链表
- 判断链表成环
- 判断链表相交
- 二叉树（节点形式）
- 递归遍历二叉树（先序、中序、后序）
- 非递归遍历二叉树（先序、中序、后序）
- 层序遍历
- 求取最大宽度
lecture05
- 二叉树
- 搜索二叉树
- 完全二叉树
- 满二叉树
- 平衡二叉树
- 二叉树递归套路（树形 DP）
- 最近公共祖先节点
- 查找（中序遍历）后继结点
- 二叉树的序列化和反序列化（先序、后序和层序）
- 折纸问题
lecture06
- 图
- 基本概念（顶点、边、无向图、有向图、邻接表、邻接矩阵、出度、入度、权重、邻接点、邻接边）
- 转换图结构
- 宽度优先遍历
- 深度优先遍历
- 拓扑排序
- 最小生成树
- Kruskal 算法
- Prim 算法
- 最短路径（Dijkstra 算法）
lecture07
- 字符串前缀树
- 贪心算法
- 安排会议顺序
- 最小字典序
- 哈夫曼编码
- 项目利润
- 暴力递归
- 汉诺塔问题
- 打印字符串全部子序列
- 打印字符串全排列
- 先手后手问题
- 逆转栈
- 数字转26进制所有结果
- 暴力背包
- N 皇后问题
基础提升班内容
lecture08
- 哈希
- 哈希的特性（一致性、抗碰撞性、离散型、高效性）
- 哈希表原理
- 找出出现次数最多的数字
- 设计 RandomPool 结构
- 布隆过滤器
- 位图
- 一致性哈希原理
- 虚拟节点技术
lecture09
- 并查集
- 岛问题
- 实现并查集
- 并行处理岛问题
- KMP 算法
lecture10
- manacher 算法
- 回文子串
- 滑动窗口
- 双端队列
- 维护最大值
- 单调栈
- 求两侧的第一个小于/大于自己的值
lecture11
- 树形 DP
- 求一棵树的最大距离
- 最大快乐值
- Morris 遍历二叉树
- 先序中序后序
- 判断搜索二叉树
- 大数据
- 低内存查找没出现过的数字
lecture12
- 大数据（资源限制）
- TOP 词汇
- 统计出现两次的数字
- 外排序
- 位运算
- 最大值
- 判断 2 的幂次
- 加减乘除
lecture13
- 动态规划
- 机器人步数问题
- 最少硬币
lecture14
- 动态规划
- 先手后手
- 象棋跳马（三维）
- 生存概率（三维）
- 凑零钱（斜率优化）
lecture15
- 有序表
- 搜索二叉树
- 树的左旋和右旋
- 平衡二叉树（AVL 树）
- SB 树
- 红黑树（不必深研）
- 跳表（多链表）