1. 为什么还要翻出2020年的算法课笔记2020年那会儿算法课几乎是所有计算机相关专业的必修硬骨头。我翻出自己当年那份2020算法课程记录不是为了怀旧而是因为最近帮几个刚入行的朋友梳理学习路径时发现很多现在被包装得花里胡哨的算法教程反而不如当年课堂上那套笨办法扎实。这份记录里没有花哨的动效演示没有三天速成的噱头有的只是最朴素的推导过程、最原始的代码实现以及踩过的那些坑。算法这门东西说到底就是用有限的步骤解决一类问题的思维训练。它解决的核心问题是当你面对一个从没见过的问题时能不能把它拆解成已知的、可计算的形式。适合谁来参考我的判断是三类人一是正在上算法课、被作业和考试折磨的学生二是工作几年后发现瓶颈在想不出解法而非写不出代码的开发者三是想系统补一补计算机基础、但被各种速成班带偏了方向的自学者。这份记录的价值不在于它有多高深而在于它完整呈现了一个普通人从看不懂到能写出来的真实过程。我当年记笔记有个习惯每学一个算法先记它长什么样再记它为什么长这样最后记我哪里写错了。这三层结构后来被证明是最有效的复习方式。下面我就按这个思路把这份记录里最核心的内容重新整理一遍补充上当年没写全的推导细节和后来工作中才想明白的实操要点。2. 算法学习的整体框架与思路拆解2.1 当年课程的知识地图长什么样2020年那门课的大纲现在回头看其实非常经典复杂度分析打底然后按线性结构→树形结构→图结构→经典算法思想的顺序推进。这个顺序不是随便排的它背后有一条清晰的认知逻辑——先学会衡量好坏复杂度再学会组织数据结构最后学会设计策略思想。复杂度分析放在最前面是因为它是后面所有内容的度量衡。没有这套语言你没法说清楚为什么快排平均比冒泡快也没法解释为什么哈希表查询是常数时间。当年我一开始觉得这部分很虚直到第一次面试被问你凭什么说这个解法更优才意识到复杂度不是考试用的是沟通用的。线性结构数组、链表、栈、队列是基础中的基础但恰恰是这部分最容易被轻视。我见过太多人上来就啃动态规划结果连用栈模拟递归都写不利索。树形结构是第一个真正的分水岭二叉树的各种遍历方式、二叉搜索树的性质、堆的实现这些内容直接决定了你后面能不能理解数据库索引、能不能看懂调度算法。图结构则是另一个维度它把关系本身作为研究对象最短路径、最小生成树、拓扑排序这些算法在工程里的应用密度极高。最后的经典算法思想部分——分治、贪心、动态规划、回溯——才是真正拉开差距的地方。这部分没有固定套路全靠大量练习形成直觉。当年课程安排在这里花了将近一半的课时现在想想非常合理。2.2 为什么手写实现比调用库函数重要得多课程里有个硬性要求所有数据结构必须手写实现不许直接用语言自带的库。当时很多人抱怨这是重复造轮子但我后来才明白这个要求的深意。手写实现的过程强迫你去思考每一个操作背后的代价。比如你手写一个动态数组就会真切地感受到扩容这个动作有多昂贵从而理解为什么初始化时预估容量很重要。你手写一个哈希表就会被迫处理冲突从而理解为什么好的哈希函数设计如此关键。这些体感是调用list.append()或dict[key]永远给不了的。更重要的是手写实现训练的是从零构建的能力。工作中你当然会用现成的库但当现成的库不满足需求、需要你改造或自研时这份能力就是分水岭。我后来参与过一个需要自定义内存池的项目能快速上手靠的就是当年手写链表和栈时积累的对指针操作的熟悉度。提示手写实现时不要追求一次写对而要刻意记录自己犯的每一类错误。这些错误模式比正确的代码更有价值。2.3 复杂度分析从会算到会估的跨越课程里讲复杂度用的是最标准的定义大O表示法关注最高阶项忽略常数系数。但真正让我受益的是后来自己悟出来的估算能力。会算复杂度指的是给你一段代码你能推导出它的时间空间开销。会估复杂度指的是在设计方案阶段你就能凭经验判断这个思路大概是什么量级。比如看到两两比较就条件反射想到O(n²)看到每次砍一半就想到O(log n)看到嵌套但内层依赖外层就要警惕是不是O(n²)甚至更高。这个跨越没有捷径就是靠大量做题和复盘。我当年的方法是每写完一个解法先不运行自己估一个复杂度写在旁边然后再实际测试验证。估错的就重点标记分析是哪里想当然了。坚持了大概两个月估算准确率就上来了。3. 核心数据结构的手写实现与避坑要点3.1 动态数组扩容策略里的数学动态数组的核心矛盾是数组本身定长但我们需要它看起来能自动增长。解决方案是当容量不足时申请一块更大的内存把旧数据搬过去。关键问题是每次扩容多少课程里讲的是倍增也就是新容量等于旧容量的两倍。为什么是两倍而不是每次加一个固定值这里有个摊还分析的计算。假设每次扩容增加固定值k那么插入n个元素的总搬迁次数是k2k3k...≈n²/(2k)均摊到每次插入就是O(n/k)当k是常数时就是O(n)。而如果每次容量翻倍搬迁次数是124...n/2≈n均摊到每次插入就是O(1)。这就是倍增策略的数学依据。手写时容易踩的坑扩容后忘记更新容量变量、搬迁时用错循环边界导致数据丢失、缩容时机判断错误导致频繁抖动。我当年就在缩容上栽过跟头——每次删除元素都检查是否缩容结果在容量临界点反复扩容缩容性能惨不忍睹。正确做法是设置一个滞后阈值比如元素数量降到容量的四分之一时才缩容到一半。class DynamicArray: def __init__(self): self._capacity 1 self._size 0 self._data [None] * self._capacity def _resize(self, new_capacity): new_data [None] * new_capacity for i in range(self._size): new_data[i] self._data[i] self._data new_data self._capacity new_capacity def append(self, value): if self._size self._capacity: self._resize(self._capacity * 2) self._data[self._size] value self._size 1 def pop(self): if self._size 0: raise IndexError(pop from empty array) value self._data[self._size - 1] self._size - 1 # 滞后缩容降到四分之一才缩到一半 if self._size 0 and self._size self._capacity // 4: self._resize(self._capacity // 2) return value3.2 链表指针操作的三行口诀链表是很多人学数据结构的第一个坎。课程里反复强调的三行口诀我至今还在用先连后断、保存后继、处理边界。以单链表删除节点为例。假设要删除节点cur的后继节点标准操作是# 错误示范先断后连后继丢失 cur.next cur.next.next # 如果cur.next是最后一个节点这里会出错 # 正确做法先保存要删除的节点再改指针 to_delete cur.next if to_delete is None: return cur.next to_delete.next to_delete.next None # 可选帮助垃圾回收先连后断的意思是在修改任何指针之前先把所有需要保留的引用保存好。保存后继是链表操作中最容易忘的一步尤其是在反转链表、合并链表这类操作里。处理边界指的是头节点、尾节点、空链表这三种情况必须单独考虑。我当年的血泪教训写了一个删除链表中所有值为x的节点的函数测试时用普通节点都通过一用头节点就崩。原因就是没有处理头节点本身就是要删除的节点这种情况。后来养成了习惯凡是链表操作先在纸上画出空链表、单节点、双节点这三种情况手动模拟一遍再写代码。3.3 栈与队列用两个栈实现队列的经典题栈和队列本身实现很简单但用两个栈实现队列这道题几乎每年都会出现在课程作业里。它的价值不在于实现本身而在于训练用受限工具组合出更强功能的思维。核心思路一个栈负责入队in_stack一个栈负责出队out_stack。入队时直接压入in_stack出队时如果out_stack为空就把in_stack的所有元素依次弹出并压入out_stack然后从out_stack弹出。这样元素的顺序就被倒了两次负负得正变成了先进先出。class QueueWithTwoStacks: def __init__(self): self._in [] self._out [] def enqueue(self, value): self._in.append(value) def dequeue(self): if not self._out: while self._in: self._out.append(self._in.pop()) if not self._out: raise IndexError(dequeue from empty queue) return self._out.pop()这里有个容易忽略的优化点不需要每次出队都把in_stack倒过来只在out_stack为空时才倒。这个细节决定了均摊复杂度是O(1)而不是O(n)。我当年第一次写的时候就是每次出队都倒结果被老师指出你这不是队列是每次都在做无用功。3.4 哈希表冲突处理与负载因子哈希表是工程中最常用的数据结构之一但手写实现能让你真正理解它的代价。核心要素有三个哈希函数、冲突处理策略、负载因子。哈希函数的目标是均匀分布。课程里常用的方法是取模法hash(key) % capacity。但这里有个坑capacity最好取质数否则容易产生聚集。比如capacity是10那么所有以0结尾的key都会落到同一个位置。取质数如7、13、31能有效缓解这个问题。冲突处理课程里讲了两种链地址法和开放寻址法。链地址法实现简单每个桶挂一个链表开放寻址法在冲突时按某种规则线性探测、二次探测找下一个空位。工程中链地址法更常见因为删除操作简单且对负载因子不那么敏感。负载因子是元素数量/桶数量它直接决定性能。负载因子太高冲突概率大增太低空间浪费。课程里建议的阈值是0.75超过就扩容。这个数字不是随便定的它是在时间和空间之间取的平衡点。我后来看一些开源实现有的用0.75有的用0.6差异不大关键是保持一致。class HashTable: def __init__(self, capacity13): self._capacity capacity self._size 0 self._buckets [[] for _ in range(capacity)] def _hash(self, key): return hash(key) % self._capacity def put(self, key, value): idx self._hash(key) bucket self._buckets[idx] for i, (k, v) in enumerate(bucket): if k key: bucket[i] (key, value) return bucket.append((key, value)) self._size 1 if self._size / self._capacity 0.75: self._resize(self._capacity * 2) def get(self, key): idx self._hash(key) for k, v in self._buckets[idx]: if k key: return v raise KeyError(key) def _resize(self, new_capacity): old_buckets self._buckets self._capacity new_capacity self._buckets [[] for _ in range(new_capacity)] self._size 0 for bucket in old_buckets: for k, v in bucket: self.put(k, v)4. 树与图从递归思维到图论建模4.1 二叉树遍历递归与迭代的取舍二叉树是递归思维的最佳训练场。前序、中序、后序三种遍历递归写法几乎一模一样只是访问节点的位置不同。但课程里特别强调必须掌握迭代写法。为什么因为递归有栈深度限制遇到极端情况比如退化成链的二叉搜索树会栈溢出。迭代写法用显式栈模拟递归虽然代码复杂但可控性强。我后来处理一个深度上万的数据结构时递归版本直接崩了迭代版本稳如泰山那次之后彻底服了。以中序遍历为例迭代写法的核心是一路向左边走边压栈走到头就弹出访问然后转向右子树def inorder_iterative(root): result [] stack [] current root while current or stack: while current: stack.append(current) current current.left current stack.pop() result.append(current.val) current current.right return result这个模板可以稍作修改就变成前序访问时机提前或后序需要额外标记或双栈法。我建议把这三个迭代版本都背下来面试和工作中都用得上。4.2 二叉搜索树删除操作的四种情况二叉搜索树BST的查找和插入都很直观但删除操作是难点。课程里把它归纳为四种情况删除的是叶子节点直接删父节点指针置空。删除的节点只有左孩子用左孩子替代。删除的节点只有右孩子用右孩子替代。删除的节点有两个孩子找右子树的最小节点或左子树的最大节点替代然后删除那个替代节点。第四种情况最容易写错。关键点是替代节点的值赋给当前节点后问题转化为删除右子树中的最小节点而这个最小节点一定没有左孩子所以退化成情况2或1。def delete_node(root, key): if not root: return None if key root.val: root.left delete_node(root.left, key) elif key root.val: root.right delete_node(root.right, key) else: if not root.left: return root.right if not root.right: return root.left # 找右子树最小节点 min_node root.right while min_node.left: min_node min_node.left root.val min_node.val root.right delete_node(root.right, min_node.val) return root我当年在这里犯的错是找到替代节点后忘记递归删除替代节点导致树里出现重复值。这个bug很隐蔽因为查找和插入都正常只有删除特定结构时才会暴露。4.3 图的表示邻接矩阵 vs 邻接表图有两种主流表示法邻接矩阵和邻接表。课程里花了整整一节课对比它们的适用场景这个对比后来在我做技术选型时反复用到。邻接矩阵是一个二维数组matrix[i][j]表示节点i到j是否有边或边的权重。优点是查询两点是否相邻是O(1)实现简单缺点是空间固定为O(V²)稀疏图浪费严重。邻接表是每个节点挂一个链表存储它的邻居。优点是空间与边数成正比O(VE)遍历邻居高效缺点是查询两点是否相邻需要遍历链表最坏O(V)。选择依据很简单稠密图用矩阵稀疏图用表。实际工程中绝大多数图都是稀疏的比如社交网络、道路网络所以邻接表更常用。但如果是小规模、频繁查询相邻关系的场景矩阵反而更合适。提示如果图的节点数超过一万基本可以放弃邻接矩阵内存扛不住。我试过一个两万节点的稠密图矩阵直接吃了几个G内存。4.4 最短路径Dijkstra的贪心本质Dijkstra算法是图论里最重要的算法之一课程里讲了两遍。它的核心是贪心每次从未确定的节点中选出距离最小的确定它的最短路径然后用它去松弛邻居。为什么贪心是对的因为所有边权非负。如果存在负权边当前距离最小的节点可能通过一个负权边被更短的路径到达贪心就失效了。这就是为什么Dijkstra不能处理负权图而要用Bellman-Ford。实现上朴素版本是O(V²)用优先队列优化后是O((VE)logV)。课程里要求两种都手写。优先队列版本的关键是懒惰删除同一个节点可能被多次入队出队时检查它是否已经确定是则跳过。import heapq def dijkstra(graph, start): # graph: {node: [(neighbor, weight), ...]} dist {node: float(inf) for node in graph} dist[start] 0 pq [(0, start)] visited set() while pq: d, u heapq.heappop(pq) if u in visited: continue visited.add(u) for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist我当年踩的坑把visited判断放在松弛之前而不是出队之后导致同一个节点被反复处理。正确的做法是出队时判断因为优先队列里可能有同一个节点的多个过期条目。5. 经典算法思想分治、贪心、动态规划、回溯5.1 分治归并排序与快速排序的对比分治思想的核心是分解→解决→合并。归并排序和快速排序是两大代表但它们的性格完全不同。归并排序是先分后合不管三七二十一先把数组对半切递归排序左右两半然后合并两个有序数组。它的分解是盲目的合并是复杂的。时间复杂度稳定O(n log n)但需要额外O(n)空间。快速排序是先治后分选一个基准把数组分成小于基准和大于基准两部分然后递归处理。它的分解是复杂的需要partition合并是简单的什么都不用做。平均O(n log n)最坏O(n²)但原地排序空间O(log n)。课程里有个经典问题为什么快排实际比归并快答案是常数因子。快排的partition操作对缓存友好而归并的合并需要额外数组拷贝。这个差异在小数据量下不明显但大规模数据下快排通常胜出。不过快排的最坏情况可以通过随机化基准来规避这也是工程中的标准做法。import random def quicksort(arr, lo, hi): if lo hi: return # 随机化基准避免最坏情况 rand_idx random.randint(lo, hi) arr[lo], arr[rand_idx] arr[rand_idx], arr[lo] pivot arr[lo] i, j lo, hi while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quicksort(arr, lo, i - 1) quicksort(arr, i 1, hi)5.2 动态规划从记忆化搜索到递推的思维转换动态规划是算法课里最让人头疼的部分没有之一。课程里用了大量篇幅讲状态定义和转移方程但我觉得最关键的一步是先写出记忆化搜索再改写成递推。记忆化搜索是自顶向下的递归加一个缓存避免重复计算。它的好处是思路直观直接对应问题的递归结构。比如斐波那契def fib_memo(n, memo{}): if n 1: return n if n in memo: return memo[n] memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]改写成递推自底向上时只需要把递归的依赖关系反过来从最小子问题开始填表def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]这个转换过程能帮你理清状态和转移到底是什么。我当年的经验是如果一道DP题你写不出递推那就先写记忆化搜索能过就行然后再慢慢优化。不要一上来就追求最优解那样容易卡死。5.3 贪心什么时候可以目光短浅贪心算法的特点是每一步都做当前看起来最好的选择不回头。它的难点不在于实现而在于证明贪心选择是正确的。课程里讲了一个经典例子活动选择问题。给定一堆活动每个有开始和结束时间选最多的不冲突活动。贪心策略是按结束时间排序每次选结束最早且不冲突的。为什么这个策略对因为结束越早留给后面的时间越多这是一个交换论证可以证明的。但贪心不是万能的。比如背包问题如果物品可以分割贪心按性价比选是对的如果不能分割0-1背包贪心就错了必须用动态规划。这个对比让我明白贪心的适用条件很苛刻用之前一定要想清楚局部最优能不能推出全局最优。5.4 回溯排列、组合、子集的统一模板回溯是带撤销的深度优先搜索。它的模板非常固定做选择→递归→撤销选择。排列、组合、子集这三类问题都可以用同一个框架解决区别只在于选择的范围和终止条件。def backtrack(nums, path, result, start): result.append(path[:]) # 记录当前子集 for i in range(start, len(nums)): path.append(nums[i]) backtrack(nums, path, result, i 1) # 组合i1排列用visited数组 path.pop()这个模板我用了无数次从课程作业到工作里的权限组合生成。关键细节是path[:]的拷贝——如果不拷贝result里存的全是同一个列表的引用最后全是空的。这个坑我踩过至少三次每次都是调试半天才发现。6. 常见问题与排查技巧实录6.1 复杂度估算速查表场景特征典型复杂度常见算法两两比较O(n²)冒泡、选择、插入每次砍一半O(log n)二分查找、平衡树操作分治后合并O(n log n)归并、快排嵌套但内层递减O(n²)某些字符串匹配状态压缩O(2^n)子集枚举、状压DP全排列O(n!)回溯、暴力搜索6.2 调试技巧从猜到证算法题调试最忌讳改一改试试。我后来养成的方法是先构造最小反例再手动模拟最后才改代码。最小反例指的是能触发bug的最简单输入。比如链表操作崩了先试空链表、单节点、双节点DP答案不对先试n0、n1、n2。手动模拟就是在纸上一步步走代码把每个变量的值写下来。这个过程很慢但能精准定位问题。我统计过手动模拟花10分钟比盲目改代码试半小时效率高得多。6.3 边界条件检查清单每次写完算法我都会过一遍这个清单输入为空空数组、空链表、空树会怎样输入只有一个元素会怎样输入有重复元素会怎样输入已经有序/逆序会怎样数值溢出整数最大值、最小值会怎样递归深度是否可能超限这个清单帮我挡掉了至少一半的bug。尤其是重复元素和已有序这两条很多算法的退化情况都藏在这里。6.4 从课程到工作的思维转变课程里的算法题通常有明确的输入输出和边界但工作中的问题往往是模糊的。我后来总结了一个转变从实现算法到识别问题。工作中没人会告诉你这是最短路径问题你需要自己从需求里抽象出图模型。也没人会告诉你用动态规划你需要自己判断子问题是否重叠、最优子结构是否存在。这个识别能力靠的就是课程里那些看似无用的算法思想训练。当年觉得贪心、分治这些概念很虚现在才发现它们才是真正迁移性最强的部分。提示如果你正在学算法不要只满足于能AC。每做完一道题问自己这道题的核心思想是什么它还能解决哪类问题我能不能把它讲给别人听这三个问题能帮你把知识从短期记忆变成长期能力。最后分享一个我至今还在用的复习方法每隔一段时间随机抽一个当年记录里的算法不看笔记从零手写一遍。写不出来的就是还没真正掌握的。这个方法很残酷但极其有效。2020年那份记录我翻来覆去写了不下五遍每一遍都有新的理解。算法这东西没有捷径但有方法而方法的核心就是动手写反复写带着问题写。