每一课,接着上一课的理解。
22 节主线建立基础,126 节专题继续深入。所有课程都有推导、手算、代码和练习;专题按先修依赖排序,也可以按目标跳学,沿课程顶部的先修链接补课。
第 01 课 · 数组:下标、遍历与修改
用 [10, 20, 30, 40] 手算读取、插入和查找。以第一个尚未标记掌握的课程为起点,支持随时跳学和复习。
接下来:空间复杂度
按同时存活的数据量计算辅助空间,分清复制、原地修改和调用栈。
数组:下标、遍历与修改
用 [10, 20, 30, 40] 手算读取、插入和查找。
先会读数据,再计算代价复杂度:先数次数,再写 O
从 6 次配对推到 n(n−1)/2,分清时间与空间。
先会读数据,再计算代价冒泡排序
逐次比较 [3, 1, 2],证明最大值为什么到右端。
在数组上建立算法直觉插入排序
保存 key 并移动元素,比较两种排序的不变量。
在数组上建立算法直觉二分查找
维护闭区间,手算命中、不存在和单元素三种情况。
在数组上建立算法直觉哈希表:用空间换查找
从两数之和的双循环推到一次扫描。
在数组上建立算法直觉双指针:为什么能移动这一边
在有序数组上找到和为 15 的两个数,并证明排除规则。
减少重复计算滑动窗口
完整推演 abba,解释为什么缩窗必须使用 while。
减少重复计算前缀和:把区间和变成相减
构造 P[0]=0,准确查询含负数的半开区间。
减少重复计算栈:保存尚未完成的事情
用括号匹配理解后进先出和空栈检查。
决定先处理谁单调栈
用 [2, 1, 4, 3] 解释批量出栈与摊还复杂度。
决定先处理谁队列:按到达顺序处理
分清入队、出队,以及为什么不用数组头部删除。
决定先处理谁堆与优先队列
手算下沉建堆,分清堆有序与整个数组有序。
决定先处理谁递归:展开、暂停与返回
逐层展开 sum(4),再从 sum(0) 向上返回。
把大问题分成小问题归并排序
拆分 [4, 1, 3, 2],再按两个指针合并。
把大问题分成小问题快速排序
跟踪 pivot、boundary 与 j,观察不平衡分区。
把大问题分成小问题图:节点、边与邻接表
把四个房间画成图,并写出包含孤立节点的邻接表。
从一列数据走进一张图广度优先搜索
跟踪队列与 visited,说明最短层数从哪里来。
从一列数据走进一张图深度优先搜索
跟踪栈和回溯顺序,用反例区分 DFS 与 BFS。
从一列数据走进一张图并查集
合并代表根,追踪 parent、size 和连通分量数。
从一列数据走进一张图Dijkstra 最短路
用 dist 表逐轮选点、松弛,并检查非负边权前提。
从一列数据走进一张图动态规划入门
由爬楼梯递归树推到 DP 表,再压缩成两个变量。
只计算一次子问题空间复杂度
按同时存活的数据量计算辅助空间,分清复制、原地修改和调用栈。
基础与数据结构Big O
用上界、下界和紧界描述增长,并说明输入条件与成本模型。
基础与数据结构字符串
分清字符、码点、字节和可见字符,避免切片与拼接的隐藏成本。
基础与数据结构链表
画出指针更新顺序,理解链表反转、插删条件和哨兵节点。
基础与数据结构集合
把集合操作转成成员判断,并解释去重、交并差与哈希前提。
基础与数据结构选择排序
区分比较与交换成本,用有序前缀证明选择排序,并识别不稳定性。
排序算法希尔排序
把间隔插入排序拆成多条子序列,理解增量序列为何影响成本。
排序算法堆排序
分清有效堆区与有序后缀,利用堆顶反复放置最大值。
排序算法计数排序
由频次表推到稳定放置位置,明确值域大小与空间限制。
排序算法桶排序
区分分桶与计数,推导分布假设如何影响桶内成本。
排序算法基数排序
用稳定性归纳证明 LSD 基数排序,处理位数、基数与非负整数约定。
排序算法线性搜索
明确返回第一个匹配位置的含义,并从失败前缀证明线性搜索。
搜索与回溯回溯
用状态、选择、约束与撤销组织搜索,区分路径与答案快照。
搜索与回溯折半搜索
把子集和拆成两半,推导指数降低与内存增加的交换关系。
搜索与回溯快慢指针
用相对速度解释环检测,再推导寻找环入口的第二阶段。
数组技巧二维前缀和
用半开坐标和容斥计算矩形和,避免重复减去重叠区域。
数组技巧差分
将区间加拆成两个端点事件,再用前缀和还原全部变化。
数组技巧区间合并
排序后维护当前最右端点,严格区分闭区间与半开区间相接的语义。
数组技巧扫描线
将区间转成排序事件,并用端点处理次序表达重叠规则。
数组技巧单调队列
用下标同时处理过期与支配关系,在线求每个固定窗口的最大值。
栈与队列进阶优先队列
将抽象操作与堆实现分开,利用稳定的优先级键处理任务。
栈与队列进阶二叉树
用空树作为递归基例,明确节点数、深度、高度与子树之间的关系。
树与范围查询前序遍历
理解先访问根的用途,并推导迭代栈为何先压右孩子。
树与范围查询中序遍历
模拟左根右的暂停状态,并解释 BST 中序有序的额外前提。
树与范围查询后序遍历
用展开标记表达先处理孩子再处理根,连接子树汇总与树形 DP。
树与范围查询层序遍历
用队列长度冻结当前层,避免把下一层混入本层结果。
树与范围查询二叉搜索树
将有序区间映射到子树,解释查找、插入与退化高度。
树与范围查询AVL 树
从高度差定位失衡,区分单旋与双旋,并在回溯时更新高度。
树与范围查询红黑树
通过黑高理解红黑树的平衡,掌握左倾版本插入中的旋转和颜色翻转。
树与范围查询字典树
按字符共享前缀,区分路径存在与完整单词结束。
树与范围查询树状数组
从 lowbit 所代表的区间长度推导树状数组的查询与更新路径。
树与范围查询线段树
用可合并的区间摘要组织查询,解释相交、包含与懒标记的区别。
树与范围查询连通分量
从一次可达搜索扩展为整图分组,正确计入孤立节点。
图算法拓扑排序
用入度表达未完成依赖,证明取出入度零节点的安全性并检测环。
图算法Bellman–Ford
用边数分层解释反复松弛,检测从源点可达的负环。
图算法Floyd–Warshall
用允许的中间节点集合定义状态,解释为什么 k 必须放在最外层。
图算法A* 搜索
将已走代价 g 与剩余估计 h 分开,理解可采纳性、一致性与重新展开。
图算法二分图
用两色约束检测二分图,理解奇环为何是不可二分的障碍。
图算法最大匹配
沿交替路径重新安排已匹配边,用增广提高配对数量。
图算法网络流
用残量边表达可追加与可撤销的流,推导增广路径和最小割证书。
图算法记忆化搜索
把递归状态作为缓存键,分清重复子问题与环依赖。
动态规划一维 DP
先定义前缀状态,再按最后一个选择推导最大不相邻子序列和。
动态规划二维 DP
用二维坐标表示依赖,推导带障碍网格路径计数及滚动数组。
动态规划0/1 背包
从二维选与不选推到容量倒序,证明每件物品最多使用一次。
动态规划完全背包
解释容量正序如何允许重复使用同一物品,区分最优值、组合数与排列数。
动态规划多重背包
用二进制拆分表达数量上限,再还原为 0/1 背包。
动态规划最长递增子序列
先建立以位置结尾的 DP,再推导各长度最小尾值的二分优化。
动态规划最长公共子序列
用两个前缀定义状态,从末尾字符是否相同推导最长公共子序列。
动态规划编辑距离
按最后一次编辑操作分类,区别删除、插入和替换对应的前缀变化。
动态规划区间 DP
按区间长度填表,枚举最后一次合并位置,理解重复区间子问题。
动态规划树形 DP
给节点设置选与不选两个状态,以后序合并互不干扰的子树。
动态规划状态压缩 DP
用位集合和终点共同描述访问状态,理解指数状态的可用规模。
动态规划数位 DP
按数位构造受上界约束的数字,分清 tight、前导零与性质状态。
动态规划贪心思想
把局部选择与全局证明连接,学会用交换论证检查一个贪心规则。
贪心策略二分答案
先构造单调可行性判定,再在答案区间找到最小可行值。
搜索与回溯最小生成树
区分连通网络的总成本与单源最短路,用割性质理解安全加边。
图算法Kruskal
按边权扫描,用并查集跳过成环边并识别不连通输入。
图算法Prim
维护一棵已连接的树,每次选择跨出边界的最轻边,并跳过过期候选。
图算法区间贪心
用最早结束时间最大化不重叠区间数量,识别加权版本的变化。
贪心策略调度问题
分清等待、周转与响应时间,依据到达条件选择调度模型。
贪心策略Huffman 编码
通过合并两个最小权重构造前缀码,并用带权路径长度衡量编码成本。
贪心策略DP 与贪心
用最小反例区分贪心选择和最优子结构,解释何时必须保留多个状态。
贪心策略KMP
用最长相等前后缀保存失配信息,让文本指针只向前走。
字符串算法Z 算法
用已知匹配区间复用前缀比较,区分 Z 值与前缀函数。
字符串算法Manacher
利用回文镜像和最右边界计算奇偶半径,避免逐中心重复扩展。
字符串算法AC 自动机
在 Trie 上添加失败链接,让一次文本扫描同时发现多个模式。
字符串算法后缀数组
用后缀排序把子串搜索转为有序查找,理解倍增排名与 LCP 的作用。
字符串算法最大公约数
从公共因子的定义理解 GCD、互质与约分,再准备更快的取余算法。
数学算法欧几里得算法
证明取余不改变公共因子集合,并用严格递减保证终止。
数学算法最小公倍数
从质因子指数解释 GCD 与 LCM 乘积关系,安全处理零与溢出。
数学算法模运算
理解同余的等价类,解释为什么模下除法需要逆元且不总存在。
数学算法字符串哈希
由多项式前缀推导子串指纹,正确处理长度与碰撞。
字符串算法Rabin–Karp
维护固定长度窗口指纹,并用原文验证把概率筛选变成确定正确的匹配。
字符串算法快速幂
按指数二进制拆解,利用循环不变量证明反复平方。
数学算法质数筛
把重复试除转成批量标记,区分单个素性判断与区间内全部质数。
数学算法埃氏筛
证明 p² 起筛和 √n 停止的依据,理解分段筛的进一步优化。
数学算法组合数
从是否选最后一个元素推导 Pascal 递推,区分组合与排列以及模逆元条件。
数学算法二分求根
用连续性保持异号区间,并把迭代次数转成可验证的根位置误差界。
数值算法牛顿求根
从切线方程推导更新,理解简单根附近的快速收敛与初值风险。
数值算法梯形积分
把积分理解为累积面积,推导端点半权重与复合梯形误差。
数值算法Simpson 积分
从二次插值推到 1、4、2 权重,理解偶数子区间与四阶误差条件。
数值算法高斯求积
同时选择节点与权重,通过矩匹配推导两点 Gauss–Legendre 求积。
数值算法Euler 方法
从变化率推导时间推进,区分局部误差、全局误差和数值稳定性。
科学计算Runge–Kutta
通过四次斜率采样构造 RK4,区分内部阶段、时间步与误差阶。
科学计算并行归约
用树形求和区分总工作量与依赖深度,理解结合律及浮点求和差异。
并行算法并行前缀和
从排他前缀和出发,手算 Blelloch 的上扫与下扫,理解工作高效的并行前缀计算。
并行算法并行排序
用双调排序网络观察独立比较交换,计算网络层数并理解它与通用排序的取舍。
并行算法矩阵乘法
先算清形状与行列内积,再用三个循环实现矩阵乘法并分析成本。
并行算法矩阵快速幂
把线性递推写成状态转移矩阵,再用二进制幂跨过大量步数。
数学算法高斯消元
用行变换消去未知数,解释部分选主元、回代与残差检查。
数值算法LU 分解
把消元过程保存为三角因子,一次分解复用多个右端项,并明确置换约定。
数值算法QR 分解
用正交投影分离列方向,推导 QR 与最小二乘的联系。
数值算法Cholesky 分解
利用对称正定结构分解 A=LLᵀ,解释正对角与平方根的来源。
数值算法离散傅里叶变换
用复指数基函数表示离散频率,明确正负号、频率索引和归一化约定。
信号处理快速傅里叶变换
把 DFT 按奇偶下标分治,推导蝶形合并与 O(N log N) 成本。
信号处理卷积
从离散乘加理解卷积,解释线性卷积、循环卷积和补零长度。
信号处理逆快速傅里叶变换
通过共轭与归一化恢复时域序列,检查符号约定和舍入误差。
信号处理梯度下降
从斜率的含义出发,推导下降方向、学习率与二次函数的收敛条件。
优化算法共轭梯度
用 A-共轭方向解决对称正定系统,区分残差、误差与收敛条件。
数值算法随机梯度下降
区分完整梯度、单样本梯度和小批量梯度,解释随机波动、抽样与步长衰减。
优化算法动量
理解速度变量如何累积梯度,并区分动量的两种缩放约定。
优化算法Adam
逐项算出一阶矩、二阶矩、偏差修正和自适应步长,辨清 Adam 与 AdamW。
优化算法牛顿优化
从二阶近似推导牛顿方向,理解正定曲率、线搜索及求根牛顿法的关系。
优化算法BFGS
用相邻两步的梯度变化估计曲率,推导割线条件与逆 Hessian 更新。
优化算法L-BFGS
用最近 m 对位移与梯度差计算搜索方向,理解双循环递推为何节省内存。
优化算法线性规划
把文字约束转换为半平面,用二维顶点理解线性规划的可行域与最优解。
优化算法有限差分法
从相邻网格点的泰勒展开推导中心差分,并把边界条件装进线性方程。
科学计算有限元法
从弱形式、帽子基函数到单元组装,亲手构造一维有限元方程。
科学计算有限体积法
围绕单元内总量推导通量更新,理解守恒、迎风方向与 CFL 条件。
科学计算时域有限差分
通过一维交错网格理解电磁场的时间推进,明确空间、时间错位和稳定条件。
科学计算分块
将矩阵乘法分成可复用的小块,理解边界块、缓存局部性和计算量不变。
并行算法通用矩阵乘
把 GEMM 写成 αAB+βC,区分形状、累加精度、数据布局与 GPU 分块执行。
AI 与 GPUSoftmax
从指数归一化推导稳定 Softmax,明确归一化轴、掩码与数值边界。
AI 与 GPU注意力
逐步核对 Q、K、V 的形状,算出缩放分数、行权重和加权输出。
AI 与 GPU反向传播
沿计算图应用链式法则,并在共享节点累加梯度,用有限差分核对结果。
AI 与 GPU算子融合
沿数据依赖判断哪些操作可以融合,比较中间数组流量与资源代价。
AI 与 GPU内存分块
通过分块转置理解合并访存、共享内存、同步和边界线程。
AI 与 GPUFlashAttention 思想
推导在线 Softmax 的重缩放公式,理解精确注意力如何避免保存完整分数矩阵。
AI 与 GPU先来先服务
按到达顺序画出甘特图,分别计算响应时间、等待时间和周转时间。
操作系统算法最短作业优先
在当前就绪任务中选择最短任务,用交换论证理解平均等待最优结论的条件。
操作系统算法时间片轮转
通过时间片与就绪队列手算抢占过程,分析响应时间和切换成本的取舍。
操作系统算法优先级调度
明确优先级约定,并用老化计算解释长期等待如何影响选择。
操作系统算法最近最少使用
把哈希定位与双向链表排序结合,实现访问更新和最近最少使用淘汰。
操作系统算法FIFO 页面置换
逐次模拟 FIFO 缺页替换,理解命中不重排,以及增加页框反而缺页更多的例子。
操作系统算法Clock 算法
手算环形指针与引用位,理解 Clock 如何用较低维护成本近似最近使用。
操作系统算法伙伴分配器
沿二叉拆分和伙伴合并模拟分配,理解按幂次对齐、异或定位与内部碎片。
操作系统算法