各章笔记
绪论
向量与列表
栈与队列
树、二叉树、搜索树
散列
图
优先级队列
串匹配
排序
知识点一览
算法问题
- 总和最大区段问题
- 动态规划求Fibonacci序列
- 最长公共子序列LCS问题
- 向量元素就地循环位移问题
- 快速幂计算问题
- (伪)随机数生成问题
- 快速计算整数二进制表示的1位数
- 更相减损术
- Hanoi问题
- 八皇后问题
- 迷宫寻径问题
- 向量逆置？
- 进制转换
- 括号匹配
- 中缀表达式求值
- 中缀表达式转后缀表达式
- 直方图最大矩形
- Steap&Queap:维护栈和队列的getMax()接口
- Huffman树的构造策略
- 圆桌骑士问题
- 旅行骑士问题
- 最低公共祖先LCA问题
- 最大缝隙MaxGap问题（桶排序思路）
- 对数密度的整数集排序（基数排序思想）
- BFS 如何在 O (n+e)内找到直径？
- 旅行商问题：找出哈密尔顿环路
知识点细节
- fib(k)二分递归实例出现次数问题
- O(√n)的形式
- 递归调用：线性递归实例分析
- 递归调用：二分递归实例分析
- 平均分析 Vs. 分摊分析
- 二分查找B和C的特点
- 二路归并排序的复杂度、优缺点与改进
- 二分搜索的平均查找长度
- 二分查找A与Fib查找对比
- 插值查找: 查找区间宽度缩减速度和整体复杂度
- 大致有序情况时归并排序的改进策略
- 基数排序的思想基础
- 选择排序的稳定性如何保证？
- 插入排序的性能、交换次数分析
- 循环节：选择排序过程中出现无需交换的情形可能有多少次？
- 逆序对与冒泡排序、插入排序
- 无序列表唯一化的最好情况是什么？
- 插入排序的比较次数
- 栈混洗：总数、禁形判断、与括号匹配的关系
- Catalan数的实例
- 中缀表达式求值实例
- 中缀表达式转后缀表达式
- 双栈当队：实现与性能分析
- 循环向量实现队列
- 树的深度与高度关系
- 二叉树度数、节点数、边数的关系
- 长子兄弟表示法：找到根的复杂度、遍历复杂度
- 满二叉树与真二叉树的区别
- 完全二叉树的定义与特点
- 先序遍历迭代版
- 中序遍历迭代版
- 后序遍历特点、迭代版
- 后序遍历应用：表达式树
- 二叉树重构的结论
- 为什么先序+后序不能唯一确定二叉树？
- 为什么真二叉树能够使先序+后序唯一确定二叉树？
- PFC解码的流程，且是在线算法吗？
- 最优编码树是真完全树？
- 考虑权重，真完全树还是最优编码树吗？
- Huffman 树的特性：双子性、层次性
- Huffman树构造的改进方案：优先级队列改进方案的时间复杂度
- 树的半径与BFS
- BST插入的节点一定是叶节点吗？
- BST删除操作的两种情况
- BST随机生成和随机组成的区别
- AVL-tree的高度与节点数关系
- Fib-AVL树的形态
- AVL-tree树高增长的可能性：一定要失衡吗？
- AVL-tree树高降低的可能性：一定要失衡吗？
- Splay-tree双层伸展的细节、单层伸展最多发生多少次？
- Splay-tree的插入：在根部直接插入节点，省去第二次伸展
- Splay-tree删除：先伸展再根部删除之
- Splay-tree的势能分析
- BTree定义的细节：深度、高度
- BTree树高、胖瘦问题
- BTree插入引起的上溢修复、树高增加的可能性
- BTree删除引起的下溢修复、下溢到根的可能
- BST结构与并发性(访问延迟)的关系
- 红黑树的高度、黑高度、黑深度、红高度
- 红黑树双红修正：黑高度增加的可能性
- 红黑树的删除操作如何引起双黑冲突
- 红黑树双黑修复：黑高度降低的可能性
- 红黑树插入、删除操作的总结
- 2的证明
- BST在n-1次旋转内就可以转换为左侧链
- 任何两棵等价BST在2n-2次调整内即可彼此转换
- AVL树何种情况下删除节点需要调整O(logn)次才会复平衡？
- AVL树删除节点后调整至某一祖先复衡，是否可以停止上溯？
- 证明递增插入2^(h+1)-1个关键码到AVL树必能得到满树
- BTree 节点插入过程中导致的分裂次数的分析
- 除余法中素数的作用、算法的缺陷
- MAD法中M、A这两个操作对除余法进行了什么改进？
- 开放散列与封闭散列的区别是什么？
- 开放散列的三种思路：多槽位、公共溢出区、独立链的特点
- 开放散列和开放定址的区别？
- 线性试探：思路、优劣、懒删除机制
- 重散列与双散列的区别:rehash, bi-hash
- 平方试探中表长是素数、合数有什么影响？装填因子多少时可以保证找到？
- 双向平方试探什么情况下可以填满整个表？
- 基数排序的时间复杂度分析
- 基数排序如何确保正确性？底层排序一定要稳定吗？
- 计数排序的应用场景、思路与实例
- 计数排序每轮迭代的最后一步——扫描数据能否改为自前向后？
- 跳转表的空间性能：塔高期望
- 跳转表查找：纵向跳转次数和横向跳转次数
- 除余法导致的关键码冲突数、散列表利用率
- 路径、环路：欧拉环路、哈密尔顿环路等概念
- 邻接矩阵：特点、空间复杂度和利用率、性能、缺点
- 邻接表：特点、空间复杂度、时间复杂度（琐碎）
- 邻接矩阵和邻接表的取舍原则
- BFS过程中顶点状态、边记号的含义
- bfs时间复杂度
- 图的最短路径思路、BFS过程中队列变化细节
- 图的偏心率、半径、直径、中心
- DFS顶点状态dTime、fTime细节、其他状态的含义
- DFS过程中边的状态细节
- 括号引理与活跃期
- DFS各自适用的场景
- 如何判断图中出现环路？
- 如何判断是否存在欧拉环路？
- DAG与拓扑排序的偏序、全序关系
- 零出度拓扑排序的应用
- 关节点、双连通图、双连通分量的定义、特点
- DFC判断双连通图：内部节点何时为关节点？hca如何判断双连通分量？
- 优先级搜索的时间复杂度
- 最短路径树的概念与Dijkstra算法的局限性
- Dijkstra算法的实例细节
- MST的蛮力算法：Cayley公式
- 极短跨边理论：排除环路最长边、容纳割的最短边的思路
- Kruskal算法的思路步骤、正确性、并查集实现
- 有向图、无向图的关联矩阵与邻接矩阵的关系
- Prim 算法通过扰动消除由重复边引起的歧义
- 合成数法消除 Prim 和 Dijkstra 算法的歧义性
- 考查负权边和负权环对 Prim 和 Dijkstra 算法的影响
- 证明 Prim 算法在多边等权时亦然成立
- 最坏情况的 Kruskal 算法
- 最短路径树唯一确定吗？
- 完全二叉堆的秩的关系：内部节点最大秩，父亲的秩，左右子的秩
- 二叉堆插入：逐层上滤步骤及效率
- 二叉堆删除：逐层下滤步骤及效率，注意ProperParent宏
- Floyd建堆法详细步骤、效率、具体比较次数、不适用场景
- 大顶堆delMin操作可以达到O(logn)吗？具体是多少？
- 胜者树细节：重赛次数、性能、用以k选取的比较次数
- 败者树细节：思路、亚军、比较次数
- 二叉堆对图PFS的改进：优劣
- 多叉堆秩的计算方式
- 多叉堆特点：堆高、下滤性能、上滤性能
- 多叉堆实现 PFS 的优势
- 左式堆的形态、实现
- npl的计算方式
- 左式堆的左倾性如何控制？左倾性的细节性质
- 左式堆节点数与高度关系：右侧链与长度、最浅外部节点
- 左式堆如何实现堆的合并
- 左式堆合并的复杂度
- 左式堆如何实现插入与删除
- 二叉堆中如何在O(1)时间确定任何祖先的秩
- [[A0-String#理解
next[]表|理解 next[] 表]] - [[A0-String#构造
next[]表|构造 next[] 表]] - KMP算法分摊分析复杂度
- [[A0-String#改进
next[]|改进 next[] 表]] - KMP算法的适用情景
- 坏字符移动的思路
- [[A0-String#构建
bc[]表|构建 bc[] 表、及时间复杂度]] - 坏字符策略的性能分析与适用场景
- 好后缀的思路
- [[A0-String#构造
gs[]表——借助最大匹配后缀串|借助最大匹配后缀串构造 gs[] 表]] - [[A0-String#如何构造
ss[]？|构造 ss[] 表的时间复杂度]] - KMP、BM-BC、BM-GS策略性能分析与比较
- 散列如何优化KR法？
- 快速指纹计算：方法、复杂度
- 轴点划分LUG版
- 轴点划分DUP版：应对情形、改进之处、特点
- 轴点划分LGU版：如何操作？
- 快速排序递归深度的分析
- 快速排序比较次数的分析：递推分析、后向分析
- 众数与中位数：关系、确定众数候选的方法
- 中位数选取：减治策略及复杂度
- k选取：基于快速化分的k选取策略、复杂度
- k选取：线性选取策略、复杂度
- 输入敏感性与希尔排序性能分析
- shell序列最后一趟复杂度为Ω(n^2)的原因
- 互素元素线性组合的最大不可表示数
- 互素步长的排序后逆序对的间距
- (g, h)-sorted 时 d-sorting 的排序成本
- PS步长序列的时间复杂度
- Pratt步长序列的时间复杂度
- Sedgewick步长序列的时间复杂度
- 如何基于中位数选取算法实现k选取？
- Pratt序列的详细分析
拓展延伸
- Stirling渐进
- Little-o-notation
- 线性规约Linear reduction
- CBA排序算法下界分析(比较树)
- 动态规划
- Fisher 随机数生成算法与分析
- 无序向量唯一化的时间下界
- 指数查找
- 马鞍查找
- 鸡蛋查找：分支深入代价严重不对称
- Bitmap
- In-place mergesort
- N-way merge
- 自调整列表
- 孪生栈
- 费马-拉格朗日分解
- Catalan数实例(14个)
- 键树Trie
- 如何证明两棵等价BBST在O(logn)时间内不能完成彼此转换
- 何种插入关键码的次序使 BTree 高度最小
- B* 树及其优点
- B+树
- Height-BBST vs. Weight-BBST
- 斐波那契序列与最差AVL树的证明
- 二分图
- Floyd-Warshall 算法求 SPT
- 欧式最小支撑树
- 并查集
- 强连通分量的求解方法
- Fibonacci-heap
- Min-max heap
- Skew heap
习题解析好题
- 分摊分析实例：二进制整数递增
- 比较树高度分析: CBA排序
- 插入多个元素到有序序列的比较次数
- 找出向量中最大者、次大者的策略优化
- 插入排序性能分析
- 逆序对与插入排序分析
- 循环节：选择排序中无需交换的元素的数量
- mergeSort不平衡划分的影响:O(n^2)
- 栈混洗与禁形
- 中缀表达式运算中根据括号数求栈规模
- 二叉树高度与节点数问题：引伸到真二叉树
- PFC 编码一定解码成功吗？
- 易错：迭代式树遍历算法的栈的最小容量
- 分析 travIn_I3 的时间复杂度（succ接口对复杂度的影响）
- 层次遍历辅助队列容量问题
- 层次遍历过程中辅助队列规模单峰对称的性质
- 如何判断任一对节点间存在“祖先-后代”关系？
- O (n)时间内判断是否树中所有节点的数值均不小于其真祖先的数值总和
- O (n)时间内将每个节点的数值替换为后代中最大数值
- 如何在关键码可重复的BST中找到目标项的全部？
- 2012个内部节点的红黑树(黑)高度的极值问题
- 证明：分摊意义上红黑树重平衡中需要重染色的节点数为O(1)
- 表长为什么不能取作2^k？
- 单向平方试探法在素数长度的哈希表中的查找链分析
- 散列表长为合数时的平方试探
- 双向平方试探的表长分析：4k+3
- 计数排序
- 单向平方试探为什么会陷入死循环
- 平面图的边数量为O(n)的证明
- BFS 辅助队列的特性
- 通过拓扑排序检查是否是 DAG
- 以 PFS 设计 prioUpdater 实现 BFS、DFS
- 边权重复时极小支撑树问题
- 如何将上滤算法的比较次数优化到O(loglogn)
- 估算 percolateUp 的实际期望
- CBA式算法构建Huffman树的时间下界
- 利用频率已有序的性质在 O (n)完成构建 Huffman 树
- 利用多叉堆改进 Prim 算法
- 为栈维护 getMax 接口
- 为队列维护 getMax 接口
- 合并大节点AVL树和小节点AVL树
- 分裂大节点AVL树和小节点AVL树
- KMP 复杂度的严谨分析
- [[A1-String-Exercise#11 -6
gs[]构造算法的时间复杂度|ss[]和 gs[]表的构造算法复杂度]] - 模式枚举问题：匹配间隔的设置对复杂度的影响
- 分析模式匹配蛮力算法的实际效率
- LGU策略能否应对大量元素重复的情况？
- 三点取中法的失衡概率计算
- 众数定义修改为“不少于一半”的分析
- [[B1-Sort-Exercise#12-7-不等长向量长度的-median-算法分析|不等长向量长度的
median()算法分析]] - 基数排序推广：希尔排序的基本思想
- 证明 g-sorted 的向量经过 h-sorting 后亦然保持 g-sorted