ts-algorithm
| 数据规模 | 算法可接受时间复杂度 |
|---|---|
| <= 10 | O(n!) |
| <= 20 | O(2^n) |
| <= 100 | O(n^4) |
| <= 500 | O(n^3) |
| <= 2500 | O(n^2) |
| <= 10^6 | O(nlogn) |
| <= 10^7 | O(n) |
| <= 10^14 | O(sqrt(n)) |
| - | O(logn) |
想到的一些关键词
-
字符串
- 大数运算
- 子序列匹配
- 字符串哈希(Rabin-Karp)
- 最小表示法
- 枚举分割点
- 循环节
- 中心扩展
- k 在数字中出现的次数
- 字符串压缩
-
数组
- 数组是存放在连续内存空间上的相同类型数据的集合
- JS 的快慢数组
- 摆动数组(Wiggle)
- 二维数组映射
- 螺旋矩阵
- 泡泡堂问题
- 矩阵旋转
- 嵌套数组
- 山脉数组
- 旋转数组
- 原地哈希
- 原地操作数组：读写指针
- 最大连续 1 的个数
- 左右扫两遍
- 延迟删除
-
栈
- 单调栈适合的题目是求解 下一个大于 xxx 或者下一个小于 xxx 这种题目
- Stack overflow :函数的临时变量存储在栈区；递归调用栈超出最大深度引起爆栈：Maximum call stack size exceeded
- 字典序删除问题
- 括号问题
- 计算器
- 相邻字符删除问题
- 语法解析问题
-
队列
- 处理 bfs
- 优先队列(操作系统任务调度)
- 单调队列：有长度限制的
子序列问题 - 双端队列(ArrayDeque、LinkedList)
-
链表(直接用 Node 来表示链表)
- 基本操作：遍历/插入/删除/翻转
- dummy 虚拟结点
- 快慢指针
- JS 原型链
- 双向链表
- | 操作 | 单链表 | 双链表 | | ---------- | ------ | ------ | | append | 1 | 1 | | appendleft | 1 | 1 | | remove | n | 1 | | find | n | 1 | - 画图/注意边界条件/类比数组 - 链表的价值就在于其不必要求物理内存的连续性，以及对插入和删除的友好 -
集合
- 滚动替换
- BitSet
- 邻接表
- 有序集合
-
字典(哈希)
- Counter
- js 的 map 是 LinkedHashMap，插入键有序
- 哈希表与双向链表
- 索引邻接表
- 哈希表与前缀和
- 双射
- 定一移二
- 负载均衡
- 散列函数、装载因子、散列冲突
-
树(分层数据抽象模型)
- N 叉树：操作 n 叉树节点的最好方法就是通过父节点来操作
- dfs 序：
把子树统计变成序列上的区间统计(发 leetcoin) - 前序/后序 dfs
- 树上 dp
- 序列化与反序列化
- Trie
- 异或 Trie
- 树状数组(离散化、差分数组实现区间更新)
- LCA
- 树的直径与重心
- 线段树
- 持久化数据结构：复用结点，immutable
- 完全二叉树:除了最后一层都满了，最后一层所有节点都在最左侧(堆就是完全二叉树)
- 满二叉树: 所有层的结点数都满了
- 二叉搜索树(BST):每个结点的键值大于左孩子，小于右孩子 基本操作(logn):插入/查找/删除/最大最小/前驱后继/某个元素的排名/第 k 大小元素 中序遍历可以得到递增的序列
- **平衡二叉树(AVL)**是对二叉搜索树的优化；二叉搜索树在极端条件下会退化为链表(logn=>n) 完全随机的数据，普通的二分搜索树很好(不平衡) 读多写少的数据，AVL 树很好 读少写多的数据，红黑树很好(红黑树牺牲了平衡性) 红黑树的统计性能更优(crud) java 中的 treemap 和 treeset 基于红黑树实现
- Python 设置最大递归深度
import sys sys.setrecursionlimit(10000)
-
图
- 邻接表、邻接矩阵
- 出度入度
- 拓扑排序、拓扑排序最大深度、拓扑排序最短路径
- 带权图最短路问题
- 带限制的最短路问题
- 第 K 短路问题
- 最小生成树
- 二分图
- 匈牙利算法
- 哈密尔顿路径
- 欧拉回路
- 环检测(有向、无向图)
- 桥和割点
- floodfill
- A 星搜索
- EK 最大流算法
- 01 bfs (deque)
- 双向 bfs
- bfs 求最大深度，dfs 求最小深度
- 记忆化 dfs
- KM 二分图最大权匹配算法
- MCMF 算法
-
堆(优先队列)
- 特殊的完全二叉树
- 最大堆/最小堆
- 位置为 index 的左侧子节点的位置是
2*index+1位置为 index 的侧右子节点的位置是2*index+2父节点位置为(index-1)>>1 - topK：离线快速排序选择/在线堆/桶排序
- 堆化操作(heapify)的时间复杂度是 O(N)
- 哈夫曼编码
- 开会问题
- CPU 调度问题
- 双参量限制问题
- 多路归并
-
排序
-
js 本身的 sort 复杂度 nlog(n) 基础:冒泡/选择/插入/希尔 高阶:归并/堆/快排
-
在 V8 引擎中， 7.0 版本之前，数组长度小于 10 时， Array.prototype.sort() 使用的是插入排序，否则用快速排序。 在 V8 引擎 7.0 版本之后就舍弃了快速排序，因为它不是稳定的排序算法，在最坏情况下，时间复杂度会降级到 O(n2)。 而是采用了一种混合排序的算法：TimSort 。
这种功能算法最初用于 Python 语言中，严格地说它不属于以上 10 种排序算法中的任何一种，属于一种混合排序算法： 在数据量小的子数组中使用插入排序，然后再将有序的子数组进行归并排序，时间复杂度为 O(nlogn) 。
-
只有归并排序要 O(n)空间复杂度，其他算法都可以原地完成
-
快排/堆排序/归并排序中只有归并是稳定的(需要 mergeTwo 过程不移动相等的元素)
-
当数据量小于 10 时，使用插入排序(稳定的)优化归并排序
-
二分搜索前提是数组有序
-
bisectLeft/bisectRight
-
排序+双指针
-
二分答案
-
二维二分
-
桶排序
-
二进制分桶
-
归并排序的 merge
-
三路快排
-
年龄排序、手机号码排序
-
-
动态规划
- dp 的维度等于 dfs 的状态数
- 01 背包
- 有序/无序的完全背包
- 滚动更新
- 出租车问题
- 打家劫舍
- jump or not jump
- 记忆化 dfs
- 二维 dp：矩形系列
- LCS
- LIS
- 交叉 dp
- 路径 dp
- 区间 dp
- 线性 dp
- 状压 dp
dfs(index,visited) - 数位 dp
- 树上 dp
- 子数组与子序列
-
贪心算法
- 排序
- 取最值
- 分类讨论
-
回溯算法
- 剪枝(优化搜索顺序、最优性剪枝、可行性剪枝、排除等效冗余、记忆化)
- 优化搜索顺序：大的先排前面
- 最优性剪枝：超过 res 立即 return
- 可行性剪枝：排除不可能的情况
- 排除等效冗余：相同分配方式每次只看第一个
- 记忆化：memo
- product、permutations、combinations
- 后序 dfs
- 枚举子集
- langford 数列
- 剪枝(优化搜索顺序、最优性剪枝、可行性剪枝、排除等效冗余、记忆化)
-
并查集
- 江湖帮派
- size 优化与路径压缩
- 反向并查集
- 并查集的权重 size
- 公因数并查集：合并一个数与他的所有因子
- 带限制的并查集：union 过程不能进行路径压缩，且有 limit 限制
- 区间并查集
- 种类并查集
-
双指针
- 定一移二
- 排序+头尾指针
- 读写指针
-
滑动窗口
- k 重复字符问题
- 前缀和与子数组
- 变长滑窗：不合题意就收缩端点
- 定长滑窗：关注两个时机
-
位运算
- Java HashMap
- 布隆过滤器
- BitSet
- lowbit
- 快速幂
- 按位异或
- 汉明重量
- 格雷码
- 枚举子集
- 原地存储信息
- 状态压缩
- 0x3f3f3f3f
-
数学
- 蓄水池抽样
- 凸包
- 叉乘：三点共线
- 卡特兰数
- 曼哈顿距离
- 逆元
- 埃氏筛
- 中位数
- gcd
- divmod
- 斯特林数
- counter 配对问题
- 约瑟夫环
- 康托展开
-
杂项
- 维护最值候选人
- 摩尔投票
- 枚举参数
- 折半枚举(最接近目标值的子序列和 值很大/值很小两种类型)
- 前缀和：把一个区间的操作变为操作区间端点
- 差分数组
- 离线查询(逐步更新/命中缓存)
- 暴力枚举
- 区间合并问题
- RMQ 问题