★ FEATURED ARTICLE 1. 先说一句这门课比刷题两个字厚重得多结课那天我盯着自己的提交记录发了一会儿呆——几十道题、几次排名起伏、无数次卡在一个边界条件上的深夜。如果给这门《ACM程序设计基础》写个总结我最想说的是它表面上在教算法和数据结构实际上在做一件更根本的事——把你从代码能跑就行的舒适区里拽出来逼着你用复杂度、最优化、边界、证明这套标尺去重新丈量每一行代码。这门课适合什么人呢想入门算法竞赛但不知道从哪条路线开始的初学者已经在刷题但纯粹靠暴力枚举、排序硬扛总是超时的朋友还有像我这样不做竞赛、但希望代码质量、思维能力都能上一个台阶的普通开发者。课程主线其实不复杂语法基础快速过一遍之后直接进入复杂度概念、排序、二分、贪心再推进到栈、队列、链表、二叉树和图论基础最后用动态规划收尾。单看目录每一章我都见过但真正让我难受也让我进步的是每一章背后那些为什么非要这样做的追问。这篇总结我就按自己的真实感受来写不讲虚的把课程里对我冲击最大的几个点、踩过的坑、以及回头看才明白的经验都摊开说清楚。2. 复杂度思维从会算到会选的那道坎2.1 起初我以为复杂度只是考试题后来才知道它是每一道题的筛子开课第一周就讲大O记号我当时心里想这不就是数学课上的函数比较吗背下来就好。直到第一次交作业手写了一个三重循环嵌套的查找自测数据量小测试点全过心里还挺得意。结果助教测例一放大到十万量级程序直接卡出了运行超时四个红字。那次教训让我重新理解了复杂度分析的意义它不是让你算完就开心的理论题而是在写代码之前帮你先判断这条路到底走不走得通。当时课上给过一个很直观的标尺一秒左右的运算量大约能承受一亿次基本操作有点浮动但作为估算很实用。于是选算法之前先看一眼数据范围数据规模 n可承受的算法复杂度上限n ≤ 10O(n!) 或 O(2^n)暴力枚举也可以n ≤ 20O(2^n)状态压缩搜索的边界n ≤ 100O(n^3)Floyd 这类算法勉强能用n ≤ 1000O(n^2) 是常见选择n ≤ 10^5O(n log n)排序、二分、线段树的主场n ≤ 10^6基本只接受 O(n)线性扫描或哈希n ≥ 10^7需要 O(n) 且常数要小有时只能数学公式直接算这个表我在课程中期几乎贴在脑子里。一道题看完先不急着敲代码而是先问一句数据给到多大我最蠢的解法要跑多少次这一问就能避掉一大半超时悲剧。2.2 常数因子的隐性陷阱复杂度相同常数不同实际表现可能差出好几倍。这是课程里我印象最深的延伸讨论。举个例子同样是 O(n log n)快速排序和归并排序在最坏情况下的表现完全不同同样是哈希表操作如果自定义了一个大量碰撞的哈希函数实际退化到 O(n) 也有可能。课程的练习里有一道统计出现次数最多的单词的问题第一版我直接用嵌套循环查重O(n^2) 理所当然超时换成 unordered_mapO(n) 就过了。后来老师补充了一句超时之后别只抱怨数据大先看看自己的复杂度是否是当前问题能接受的下限能压复杂度就压复杂度压不下去再去抠常数。当时觉得这话平淡后来刷题越刷越有体会。**很多时候卡你时间的不是机器慢而是你选了一个不在可接受区间内的算法。**从那以后我每道题提交前都会用数据范围反推一下预期复杂度再决定是自己写还是去查资料。这个过程就是从跑得动就行到跑得漂亮才行的关键转变。3. 排序、二分、贪心三个看似简单、实则刀刀见骨的内容3.1 排序不只是调用 sort课程前面很大篇幅花在排序上我当时有点不耐烦排序不是一行sort()就解决了吗后面被打脸了。首先你至少得知道常见排序的本质和稳定性冒泡、选择、插入、归并、快排、堆排。课程要求手写归并排序理由是它不仅是排序还是求逆序对、理解分治思想的载体手写快排则要关注分区函数的边界和退化情况。这些不自己写一遍光靠背结论遇到变式题会非常虚。其次稳定的自定义排序是所有结构体排序的基础。有一道练习是按分数从高到低排分数相同按学号从小到大我第一版直接用了比较函数结果被指出比较逻辑没写严格弱序——即比较函数返回a b而不是a b否则排序行为未定义。这种细节课程里反复强调因为竞赛题和面试题都喜欢在比较器上做文章。最后是排序衍生出的重要思想有序性就是可检索性。一旦序列有序就可以二分可以双指针很多 O(n^2) 的问题能顺势降成 O(n log n)。没有这层意识后面学二分时容易把它当成一个孤立技巧而不是排序之后自然长出来的工具。3.2 二分法的真正难点边界到底怎么定二分查找的模板我背得很熟但做题还是错。错在哪儿基本都错在边界和循环不变式上。当时有一道寻找第一个大于等于 target 的位置的题我写成int l 0, r n - 1; while (l r) { int mid (l r) / 2; if (a[mid] target) r mid; else l mid 1; }这个写法没问题。但我自己改着改着就把else那边写成了l mid一旦区间缩不动就死循环。课程里给出的一个解决思路是写二分之前先明确你维护的区间到底是什么性质——左边是不满足条件的区域右边是满足条件的区域循环结束时左右逼近同一个边界。有了这个不变式边界条件就不是靠猜而是靠推导。二分真正的威力在于它不限于有序数组还可以用于值域二分、答案二分。比如求最小可行值这类最大化最小化问题判断函数是单调的就能通过二分答案把问题转换为验证问题。这个思路当时开了一扇门很多原本觉得无从下手的题突然有了统一的武器。3.3 贪心看起来好写证明起来要命贪心算法是我在课程里反复翻车的板块。原因很简单直觉上觉得每次取最优就能得到全局最优可一旦直觉错了就会在某一个测试点上卡到怀疑人生。课程给的经典例子是区间调度问题——给一堆区间选尽量多的互不相交区间。贪心策略是按区间右端点排序每次选结束最早的区间。策略本身一句话但你得证明它是对的结束得越早留给后续区间的余地越大因此不会劣于任何其他选择。这种证明训练比算法本身更重要。后来我刷到一道最少硬币数类问题直接按面额从大到小贪心结果很快就被反例教育了——在某些面额组合下贪心并不能得到全局最优必须用动态规划。这个教训让我明白贪心不是不能做而是做之前必须先想清楚局部最优是否真的导向全局最优多想一层的代价永远比在错误方向上debug到深夜小。4. 栈、队列与链表从数据结构课上的名词到解题时的肌肉记忆4.1 原来先进后出能解决这么多问题栈的四个操作我背得滚瓜烂熟push、pop、top、empty。但直到课程里讲括号匹配和单调栈之前我一直觉得栈只是编译原理里的配角。括号匹配那题很经典思路清晰且标准遇到左括号入栈遇到右括号出栈并检查匹配。真正让我有收获的是单调栈这一变形——它用来解决找每个元素左边比它大的最近位置这类问题。刚开始我很困惑为什么需要这样一套结构后来自己模拟一遍就明白了栈里维护的是一个候选答案序列因为左边所有被当前更大元素挡住的比它小的元素以后也永远不可能是答案。这一下就把暴力 O(n^2) 变成了 O(n)。这是我第一次感受到结构的力量**数据结构不是装饰它是在帮你在空间和时间之间做交易用额外的存储换掉重复的比较。**单调队列解决滑动窗口最值本质也是一样的思路队列里维护的可能成为答案的候选值过期就弹出于是每次取最值是 O(1)。4.2 链表、数组和删除的微妙差异链表那章节我一开始觉得就是指针玩来玩去离实际很远。直到练习里出现了设计一个支持在任意位置插入、删除的数据结构这类题才意识到数组和链表在插入删除上的代价差别是真实存在的数组插入平均要移动 O(n) 个元素链表理论上只改指针 O(1)。但课程里也反复提醒链表的 O(1) 是在你已经有目标位置指针的前提下成立。现实中如果每次都要先遍历找到那个位置那总代价还是 O(n)。所以不要迷信链表插入快这句口诀得看场景。那段时间我还踩过一个很丢人的坑手写链表删除节点delete()时必须先保存后继指针再释放当前节点否则就悬垂了。这种细节学过和没学过的区别在压力测试面前特别明显。5. 二叉树与图论入门第一次理解递归不只是语法5.1 树的所有操作都在跟递归打交道学二叉树的时候递归遍历的三行代码我背得滚瓜烂熟void dfs(TreeNode* node) { if (!node) return; dfs(node-left); cout node-val ; dfs(node-right); }中序、前序、后序顺序我都记住了但真正的坎在于能不能用迭代方式重写这些遍历。课程里那道不用递归做中序遍历的题我卡了很久。它要求显式维护一个栈模拟递归调用的过程。做完之后我才真正理解递归背后的调用栈到底是个什么东西每一个函数调用都会把当前状态压栈返回时弹栈。理解了这一点后面学回溯、学DFS时就不怕了。树的题目给我的另一个启发是**很多树的题都有一个通法——先想清楚你希望子问题返回什么再想当前节点怎么利用子问题的答案。**这个先设计返回值再写递归体的思路后来我不仅用在树上也用在整个动态规划的章节里。5.2 图的存储与能走多少步的搜索题图论基础课内容不多但很关键邻接矩阵、邻接表、DFS、BFS、最短路的简单入门。邻接表是竞赛里的主流存储方式因为稀疏图用矩阵会浪费大量空间。我当时以为学到了新东西其实这只是把每个节点所有邻居的列表存起来本质不复杂。BFS 给我开了另一个眼界它天然能求无权图的最短路径。原因是队列先进先出保证了节点按层次顺序被访问第一次到达某个节点时的步数就是最少步数。课上练习走迷宫最短路径时我用 BFS 一遍过了当时觉得不过如此直到我回头看自己最早用 DFS 暴力搜的版本——搜索路径深不见底、还容易重蹈走过的格子——才明白 BFS 这道层次扩散思想的可贵。DFS 和 BFS 的选择也成了我的一个习惯求是否存在路径用 DFS 更直观求最短步数第一个想到 BFS求所有可能性则 DFS回溯。这种思维上的分类比多背几道模板重要得多。6. 动态规划整门课最难啃也是收获最大的一座山6.1 从递归重复计算到记忆化的顿悟时刻动态规划是课程的压轴模块也是劝退率最高的部分。我第一遍学的时候完全懵状态转移方程是什么为什么看完题解觉得理所当然自己做就毫无头绪后来让我开窍的是一道斐波那契数列变式题。用朴素递归写int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }n40 已经卡到令人发指因为存在大量重复计算。随手加一个数组缓存中间结果之后瞬间变成线性int memo[10005]; int fib(int n) { if (n 1) return n; if (memo[n]) return memo[n]; return memo[n] fib(n - 1) fib(n - 2); }这个改动让我看见了动态规划的地基把递归中重复计算的子问题结果存下来空间换时间。从自上而下记忆化搜索到自下而上填表只是同一个思路的两种方向。一旦理解了这一点再去学背包问题、最长公共子序列就不是背方程而是设计状态推导转移。6.2 状态设计动态规划里最反直觉的一步课程里反复强调动态规划最难的不是循环怎么写而是状态怎么定义。我自己的瓶颈也在这。拿最长上升子序列来说——如果你把状态定义为前 i 个数的最长上升子序列长度转移会缺胳膊少腿但如果定义成以第 i 个数结尾的最长上升子序列长度转移就很自然枚举前面所有比当前小的 jdp[i] max(dp[i], dp[j] 1)。这个绕一下弯的设计恰恰是DP的核心功夫。我还总结了一个很笨但实用的学习方法**每道DP题先画一个状态表格横轴是阶段纵轴是状态变量表里填局部最优值。**以前觉得这样很浪费时间后来发现正是这个过程逼着我把题目抽象成阶段—状态—决策三个要素。到课程后期我面对一道新题不再像最初那样对着样例发慌而是先尝试问自己我要记录哪些信息才能支持后面做决策这个信息就是状态维度的来源。6.3 背包问题家族同一个骨架的多种变体背包问题是DP里最成体系的一块课程把它讲透了0/1背包每个物品选或不选倒序枚举容量避免重复选完全背包每个物品无限选正序枚举容量多重背包每个物品有限个二进制拆分优化分组背包每组物品只能选一个组间枚举。当初我把0/1背包和完全背包合在一起背总觉得正序倒序是死记硬背。后来自己在草稿纸上模拟了一遍滚动的 dp[j]更新过程才真正明白**倒序是因为更新dp[j]时只能使用上一轮的结果正序则会原地覆盖导致同一个物品被多次使用。**这一下子把 为什么倒序变成了顺理成章的事而不是死记的规则。背包问题的启示还在于它让我知道DP不是文科背诵而是理科推导从状态定义出发每一步转移都有明确的现实语义。只要语义对了代码怎么写都不会错语义不通照着模板写也可能挂。7. 刷题之外的三笔隐形财富调试、对拍和代码习惯7.1 调试能力是被题目逼出来的课程中期开始题目规模变大样例经常只有一两个剩下的靠隐藏数据。这就逼着你不能只靠肉眼读代码找错必须学会系统调试。我从那段时间积累了几个非常实用的习惯分块打印中间变量。不要整个程序一口气跑完而是把循环里关键位置的变量打出来对照手算小数据几轮下来就能定位错误范围。写小规模暴力算法做参照。比如先写一个 O(n^2) 的朴素解法再写一个高效的 O(n log n) 写法随机生成小数据反复对拍。两边结果不一致时高下立判。注意边界输入。n0、n1、全是相同元素、全是逆序元素这些数据最容易暴露问题。我后来做题提交前都会专门构造几个最极端的边界测试。这些方法没有一个被课程单独拎出来讲但它们确实是被一轮轮的WA错误答案、TLE超时硬生生逼出来的。结课回头看我认为这是比算法模板更保值的能力。日常生活里写普通业务代码这些调试手段照样用得上以前出了问题就 print 大法从头打到尾现在会画调用栈、找二分边界、用最小用例复现效率差距非常大。7.2 从乱写一气到有意识地结构化课程里很多题目代码量不算大但如果你不按结构化思路写后期图论题和DP题一定会乱。我自己经历了一次典型的重构翻盘最初写题我是想到哪写到哪函数也懒得拆变量全用 a、b、c 这种短名。结果一道稍微复杂的题调试时根本分不清某个变量是干吗的。后来强迫自己按照读入数据—预处理—核心算法—输出结果的框架组织代码把核心逻辑单独抽成函数变量名尽量语义化比如dp[int][int]、graph、visited。整理完之后代码长度没变但维护难度下降了一个量级。竞赛里一次写对的概率和代码可读性高度相关这不是玄学是实践下来的经验。还有一点是模板化积累。二分查找、快速幂、并查集、最短路这类高频模块我会在本地维护一个自己的代码片段库用时直接抄底子再按题目微调。这个习惯帮我省了很多重复劳动而且因为模板是自己反复验证过的出错的概率也小得多。8. 回头看如果重新学一遍我会怎么安排时间和策略结了课复盘自己走过的弯路我觉得如果再来一次有些策略从一开始就会不同。第一前期就要建立复杂度的主动意识而不是等超时了才回头补课。最有效的做法是每道题读完之后先在草稿纸上写一句话n的范围是10^5所以我的算法应该控制在O(n log n)以内。 这句话会直接帮你排除掉一大半不靠谱的想法。第二难题要舍得花时间但不到底就放弃。我前期遇到不会的题常常直接看题解看完就以为自己懂了结果下次遇到同类变式还是不会。后来老师建议给自己设一个思考死线比如半小时到一小时想不出来再去搜思路但搜完必须合上答案自己独立写一遍。这样做的效果非常明显因为看懂和能写对之间还隔着一道鸿沟只有亲手写才能填上。第三多和同学对题目交流。我们当时组织了一个小圈子每周固定讨论几道题。有人给出一个我完全没想过的状态设计或者一个巧妙的贪心证明那种冲击比自己埋头刷十道题都大。后来我还把自己的解题笔记整理成了带思路和坑点的文档再回头看时复习效率比翻提交记录高得多。第四适当跳出课程节奏给自己留沉淀期。这门课信息密度很高如果每天只追着新知识点跑很容易在动态规划时崩盘。我自己的经验是每隔两周回头重新写一遍之前的题目不照着代码纯靠记忆和思路去重写。这个回忆式重构的过程比盲目刷题更能检验自己到底有没有掌握。9. 最后聊两句这门课留下的东西结课那天我整理自己的代码片段库和笔记发现半年下来累积了不少东西。但比这些更重要的是一种面对未知问题时的底气我不再害怕一道没见过的题因为我有一个可以依赖的分析框架——先把数据范围读清楚估算复杂度再想最朴素的解法看看瓶颈在哪然后从数据结构、算法策略、DP三个方向分别寻找优化空间最后在写代码之前先验证自己的思路在最坏情况下能不能跑得动。这种分析框架的养成我认为才是《ACM程序设计基础》这门课最核心的回报。它不会直接给你一个工作岗位上的技能标签但它给了你一种程序员的专业直觉——看到问题不慌、动手之前有判断、写完代码有验证。刷题退役之后很多算法细节我可能都会慢慢变淡但先想复杂度、再动手写代码边界条件永远单独测调试先做最小复现这些思维习惯会一直留下。如果你也准备学这门课或者正在中途被动态规划折磨得怀疑人生我想说前面那些看起来很遥远的难点其实是可以用清晰的思路和足够的耐心拆掉的。遇到卡住的地方别死磕到天亮放一放回去看看前面的基础题往往会突然悟到点什么。这门课不简单但认真走完值。
阅读完成 · 觉得有帮助？
