东华大学2020考研计算机OJ题目解答分享——进阶篇4说实话每年到了三四月份总有一批考研人卡在复试上机这一关。初试考得再高上机一塌糊涂照样可能被刷。东华大学的复试OJ题整体难度在211院校里算是中坚水平不卷到让你怀疑人生但也绝对不是随便背背模板就能过的。之前我已经写了基础篇和进阶篇的前三部分今天这篇进阶篇4主要聊几个高频考点的深挖方向链表类操作、树的遍历变体、图论入门题、以及区间DP。这些都是2020年东华复试里出现过的类型也是考研复试上机题里最常被拿来“卡人”的几个知识点。这篇内容不是把代码贴出来就完事我会把每道题的解题思路、为什么这么做、代码里容易踩的坑全部拆开讲。不管是准备复试的考生还是想拿OJ题练手的在校生哪怕是工作上需要补算法基础的朋友这篇都能给你点实在的参考。1. OJ复试到底在考什么读懂题目背后的意图很多人刷OJ有个误区以为刷得越多越好或者以为把某本算法书的例题背下来就能稳过。实际上考研复试的上机题和竞赛题、大厂笔试题的侧重点完全不同。竞赛题追求的是思维的极限和代码的极致优化大厂题看重工程实现能力和边界处理而考研复试上机题的核心就一句话考察你有没有扎实的数据结构和算法基本功。1.1 上机考试和笔试的本质区别笔试你可以写伪代码可以只写思路甚至可以把代码写得乱七八糟只要关键逻辑对就能拿分。但上机考试不是这样你提交的代码会经过OJ系统的编译、运行然后用预设的测试数据对你的程序进行一一比对。任何一个细节出错可能就是0分和满分的区别。东华大学的OJ系统用的是标准的ACM评测模式也就是说你的程序必须从标准输入读数据向标准输出写结果格式严格遵循题目要求。多输出一个空格、少输出一个换行都可能导致Wrong Answer。这一点每年都有不少同学吃亏平时在自己电脑上跑得好好的一提交就是WA最后发现是输出格式的问题。还有一个容易被忽略的点OJ系统对代码的运行内存和运行时间都有严格限制。东华复试的OJ一般会给1秒的运行时间和64MB或128MB的内存限制。也就是说你的算法不仅要正确还要足够高效。写个三重循环处理10万级别的数据大概率就是Time Limit Exceeded。1.2 OJ评分机制与常见提交结果这里整理一下OJ提交后可能会出现的几种结果每个经历过上机考试的人都应该烂熟于心提交结果含义出现原因Accepted通过代码在所有测试点上均正确Wrong Answer答案错误逻辑有漏洞某个测试点没过Time Limit Exceeded运行超时算法复杂度过高或死循环Runtime Error运行时错误数组越界、除零、栈溢出、空指针Memory Limit Exceeded内存超限申请了过大的数组或空间Presentation Error格式错误输出格式与题目要求不完全一致Compile Error编译错误语法错误或者头文件缺失了解这些结果的含义很重要因为很多时候你的程序报错并不是因为“代码不对”而是某种特定类型的错误。比如Runtime Error很多新手第一反应是“我的思路没问题啊”但实际上可能是数组开小了越界访问导致程序崩溃。这种问题在本地测试时不一定能发现因为本地数据量小碰巧没有越界到非法地址但OJ的测试数据一上来就原形毕露。1.3 进阶篇的定位从“会写”到“写得对”前面基础篇和进阶篇1到3覆盖了输入输出处理、数组与字符串、基础排序查找、简单模拟、结构体与文件读写这些内容。到了进阶篇4默认你已经能独立完成大部分基础题现在要解决的是那些需要一点“算法设计”的题目——也就是说不光要靠翻译题目描述还要自己设计一个合理的算法流程。这类题的共同特点是单纯的暴力枚举能做但性能不够用高级数据结构和经典算法模板又能明显感觉到时间空间的改善。这就考察你有没有“把题目抽象成经典模型”的能力。比如看到“判断链表是否有环”你要能想到快慢指针看到“求二叉树两节点的最近公共祖先”你要能想到递归自底向上的解法看到“给一堆任务和依赖关系”你要第一时间反应出拓扑排序。这个阶段刷题不能再盲目追求数量了。一道题吃透比你稀里糊涂做十道题有用得多。2. 高频考点地图进阶算法的主战场结合东华大学历年的复试题目和同类院校的出题风格进阶阶段需要重点掌握的知识点其实相对集中。我把它们分为四大块链表、二叉树、图论入门、动态规划。这四个板块并不是说每年都会各出一道题而是说它们在题目中反复渗透——可能一道题表面上是在处理字符串实际上需要你构建哈希表可能一道题表面上是在模拟某个过程本质上是在考栈和队列的应用。2.1 链表与指针操作陷阱链表是数据结构的入门内容但也是上机考试的高频考点。原因很简单链表最能检验你对指针和内存管理的理解。很多同学在纸上能画出链表反转的过程一写代码就各种指针乱飞最后程序直接崩溃。链表题目常见的考察形式有链表反转、链表排序、判断链表是否有环、找链表中间节点、合并两个有序链表、删除链表倒数第N个节点。这些题目单独拿出来都不难难点在于它们经常被组合起来考。比如反转链表的一部分、对链表进行插入排序、判断两个链表是否相交等。写链表题最重要的是画图这是所有算法老师都会强调但很多学生不听的方法。你心里想的是“把当前节点的next指向前一个节点就行了”但如果没有把指针变化的顺序理清楚代码写出来就是错的。拿反转链表举例你需要三个指针prev、cur、next。每一步先把next保存下来再让cur-next指向prev然后prev和cur分别向后移动。这三个指针的更新顺序错一步链表就断了。2.2 二叉树与递归思维二叉树题目80%考的是递归遍历的变体。前序、中序、后序、层序遍历是基本功进阶的考法是根据遍历序列重建二叉树、求二叉树深度、判断二叉搜索树、找最近公共祖先、计算路径和等。二叉树题目对很多人的难点不是算法本身而是递归思维没有建立起来。很多同学看到一个二叉树题目第一反应是“我该怎么用循环实现”然后越想越复杂。实际上二叉树题目的正确打开方式是先假设我们已经解决了子问题然后考虑当前节点应该做什么最后把子问题的结果拼起来。这个思维转换非常重要。你不需要关心整棵树的完整处理过程只需要关心“当前层”发生了什么剩下的交给递归。2.3 图论入门建图与遍历图论在考研复试中不会考特别难的题核心就几个图的存储邻接矩阵和邻接表、深度优先搜索DFS、广度优先搜索BFS、拓扑排序、最短路径Dijkstra算法、最小生成树Prim和Kruskal算法。其中最容易考的就是拓扑排序因为它可以和实际场景结合得很好——课程安排的先后顺序、编译环境的依赖关系、任务调度的优先级。而且拓扑排序的代码量不大逻辑清晰很适合作为上机题出现。图论的另一个重点是建图的方式。很多题目并不会直接告诉你“这是一道图论题”需要你自己把问题抽象成图比如把每个位置看作一个节点、把每一步可达的移动看作一条边。这种抽象能力只能通过多做题来培养。2.4 动态规划从暴力的泥潭里跳出来动态规划是上机考试里区分度的关键。简单题基本人人会做但稍微加一点变化就能淘汰掉一大批只会套模板的考生。复试阶段常考的DP类型有背包问题01背包、完全背包、最长上升子序列、最长公共子序列、区间DP、状态压缩DP较少考。学习DP最忌讳的就是“背转移方程”。你要搞清楚的是“为什么这个状态转移是对的”要弄清楚dp[i][j]表示的是什么以及它为什么能从dp[i-1][j]和dp[i][j-1]转移过来。只有真正理解了状态定义和转移逻辑遇到新题才能灵活变通。3. 典型题目深度解析从读题到AC的全程拆解下面我会结合几道典型的进阶题把从读题、分析、编码到调试的完整过程走一遍。这些题目的类型在东华2020级复试里都能找到对应我也会在每道题后面标注它考察的核心知识点。3.1 链表类真题环形链表入口节点快慢指针题目描述给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回NULL。这道题考察的是链表操作和双指针技巧它的前置版本是“判断链表是否有环”大家应该都熟悉用快慢指针来解快指针每次走两步慢指针每次走一步如果两者相遇就说明有环。但题目升级到了“找到环的入口”就不是简简单单判断有环就够了。这里用到一个非常有名的数学结论从链表头部到环入口的距离等于从快慢指针相遇点到环入口的距离。也就是说在快慢指针第一次相遇之后把一个指针移回链表头部另一个指针留在相遇点然后两个指针都每次走一步它们相遇的位置就是环的入口。为什么可以简单推导一下。设链表头部到环入口的距离是a环入口到相遇点的距离是b相遇点继续走到环入口的距离是c环一圈的长度就是bc。快慢指针相遇时慢指针走了ab快指针走了abk(bc)其中k是快指针在环里绕的圈数。因为快指针的速度是慢指针的两倍所以有2(ab) abk(bc)化简得a k(bc) - b (k-1)(bc) c。这意味着从相遇点走c步到环入口再走若干整圈也回到入口同时从头部走a步也是到入口两者会在入口相遇。编码的时候要注意几个细节。第一判断快指针下一步是否为空因为快指针一次走两步要连续检查fast和fast-next是否为空指针。第二如果链表中只有一个节点或者没有环要及时返回NULL避免死循环。第三用快慢指针相遇作为“有环”的判据然后在同一函数里完成找入口的逻辑不需要额外标记节点。3.2 树类真题二叉树的最近公共祖先递归法题目描述给定一个二叉树找到该树中两个指定节点的最近公共祖先。这里说的公共祖先是指对于有根树T的两个节点p和q最近公共祖先表示为一个节点x满足x是p和q的祖先且x的深度尽可能大。这道题在LeetCode上是236题也是各大高校复试的常客。它的经典解法很巧妙用的是递归的自底向上思维。递归函数的功能是在以root为根的子树中查找p和q的最近公共祖先。如果子树中包含p就返回p包含q就返回q如果p和q都在当前节点的左右子树中那么当前节点就是它们的最近公共祖先。代码的逻辑是这样的如果root为空或者root就是p或q本身直接返回root。然后递归地在左子树和右子树中查找。如果左子树返回的结果非空右子树返回的结果也为非空说明p和q分别在当前节点的左右两侧当前节点就是它们的最近公共祖先。如果只有一侧非空则返回那一侧的结果。理解这个递归的关键在于你不用去思考“整个递归过程是怎么跑完的”你只需要关心当前这个节点在做什么。当前节点要做的就三件事查左、查右、根据左右结果做出判断。这道题最容易出错的地方是思维惯性——拿到树就层序遍历拿着队列就开始BFS。但其实这种“找最近公共祖先”的经典考法用BFS反而麻烦。递归解法代码简洁逻辑清晰在网上被称为“二叉树的浪漫解法”其实数学本质就是分治。3.3 图论真题课程表问题拓扑排序判环题目描述你总共需要选修numCourses门课程记作0到numCourses-1。在选修某些课程之前需要一些先修课程。给定课程总量以及先修课程对列表prerequisites请你判断是否可能完成所有课程的学习这道题是LeetCode上的207题考察的知识点就是拓扑排序。它的套路非常经典构建一个邻接表表示课程依赖关系然后通过BFS或者DFS来检测这个有向图是否存在环。如果存在环说明无法完成所有课程不存在环则一定可以找到一种合理的选课顺序。BFS版本的思路很直观先说清楚先统计每个节点的入度入度为0的节点就是“没有先修课程”的课程可以直接学习。把它们放进队列。每次从队列里取出一个节点相当于“学完了一门课”此时它的所有后继课程的入度都要减1一旦某个后继课程的入度变成0就说明它的所有先修课程都已经修完可以入队。最后如果入队的节点数量等于总课程数说明所有课程都能完成即无环。这里有一个容易出错的地方是邻接表的建法。初学者往往习惯用二维数组存储图但课程数量可能会很大二维数组可能直接爆内存。正确的做法是用vector数组或者用vectorvector 模拟邻接表。每个元素存储当前节点的所有后继节点。拓扑排序的另一个常见考点是“字典序最小的拓扑序”东华复试偶尔会把难度往上提一点。解法也很简单就是把队列换成优先队列每次取出编号最小的入度为0的节点。这个变体你在掌握了基础版之后一定要自己动手写一遍。3.4 动态规划真题最长回文子串中心扩展与区间DP题目描述给定一个字符串s找到s中最长的回文子串。这道题可以说是动态规划和字符串处理结合的经典例题。回文串就是正着读和反着读都一样的字符串比如“aba”、“ccbbcc”。求最长回文子串有三种主流解法暴力、中心扩展、以及马拉车算法Manacher算法。复试阶段你熟练掌握中心扩展和区间DP就足够了。中心扩展的思路是回文串一定是关于某个中心对称的所以可以枚举每一个中心点然后向两边扩展判断能扩展多长。这里的细节在于回文串的中心可能是一个字符奇数长度也可能是两个字符中间偶数长度。因此需要对每个位置分别按奇数和偶数两种情况去扩展取两者的最大值。以字符串“babad”为例枚举到字符‘a’下标1时奇数扩展能到“bab”长度为3偶数扩展时检查s[1]和s[2]是否相等这里是‘a’和‘b’不相等所以长度为0。最终遍历完所有位置最长的长度就是3。区间DP版本的思路更要讲透。定义dp[i][j]表示s[i]到s[j]这一段是否为回文串那么有当s[i]等于s[j]且s[i1]到s[j-1]是回文串时dp[i][j]为真。关键点是遍历顺序——不是从头到尾按i枚举而是按子串长度从小到大枚举也就是先计算长度为1和2的短子串再逐步推导长度更长的子串。因为dp[i][j]依赖于dp[i1][j-1]这是一个长度更短的子串必须保证它已经被计算过。区间DP这个“长度从小到大枚举”的思路是很多新手最容易卡住的地方。你如果按照i从小到大、j从小到大这么双层循环去遍历那么计算dp[i][j]时dp[i1][j-1]很可能还没算出来结果就全错了。所以区间DP的遍历顺序永远是第一层循环枚举长度第二层循环枚举起点。4. 上机实战中的常见Bug与排查技巧前面讲了这么多知识点但真正到了考场你会发现很多题不是你不会做而是代码写完了却一直AC不了。这里我整理几个在东华复试上机里最常踩的坑还有对应的排查思路。4.1 Runtime Error的隐藏原因与排查Runtime ErrorRE是复试上机里最让人头疼的报错因为本地编译运行可能完全正常一提交就崩。最常见的RE原因是数组越界。比如给数组开了100个元素的空间题目数据范围却是1000访问下标999的时候直接越界。这种情况在本地小数据量测试时可能碰巧没出错但OJ测试数据一跑就崩。排查RE的技巧有两个第一看到RE第一时间去检查所有数组的大小定义看看是不是严格按照题目给的数据范围翻倍或者动态申请了足够的空间。第二养成习惯所有涉及到数组下标的运算加到最前面打一行printf调试把当前下标打印出来跑一遍越界位置就一目了然了。另一个容易忽略的RE原因是递归层数过深。比如二叉树在最坏情况下会退化成一条链递归深度达到节点总数N。如果N是10万递归函数里没有加额外的优化很容易爆栈。解决办法是明确题目数据规模如果树可能很深就改成非递归的显式栈DFS。4.2 Time Limit Exceeded的优化方向遇到TLE先不要急着换算法分两步走。第一步看你的代码是不是有死循环。链表题目尤其容易出现这个问题指针移动条件写错循环无法终止程序卡在里面出不来。一旦超时先检查所有while循环的终止条件。第二步才是考虑优化算法复杂度。一个非常实用的优化技巧是“空间换时间”。比如判断一个元素是否在集合里用线性查找是O(n)但如果用哈希表就是O(1)。很多题目数据量一大线性查找直接TLE换一个unordered_map立马AC。另外输入输出优化也非常关键。复试OJ用的通常是C的cin/cout如果你没有加一行ios::sync_with_stdio(false)和cin.tie(NULL)在数据量较大的题里照样可能卡TLE。这是所有刷OJ的人都应该牢记在心的调优手段。4.3 Wrong Answer的边界用例测试Wrong Answer的原因千奇百怪但绝大多数都可以通过构造边界用例来排查。常见的边界用例类型包括最小值、最大值、空输入、单元素输入、重复元素、已经有序的输入、完全逆序的输入。举个例子写一个找数组最大值的程序很多人的初始代码会把maxValue初始化为0。如果题目给的数组全是负数那么最大值也是负数初始化成0会让最终结果变成错误的0。这就是典型的边界用例没有考虑到。这种问题本地测几组正常数据发现不了一提交就WA。所以每道题写完不要急着提交先自己构造5-10组边界数据去验证。我在复试前刷题时习惯在代码注释里写上“测试用例”四个字然后列几组特殊数据每次写完代码先跑一遍再提交。这个习惯帮我避免了很多次无意义的提交扣分。4.4 善用printf调试法很多学生写代码遇到bug第一反应是打开IDE的断点调试。但在OJ考试环境下每分每秒都很宝贵断点调试的效率其实很低。我更推荐一种老派但非常有效的方法printf调试法。具体操作是在关键逻辑的每个分支里加上printf语句把变量的值打出来观察程序的实际运行流程是否符合预期。比如递归函数里进入函数先打印一层“进入递归当前节点值是xxx”退出时打印“当前节点返回值是xxx”。这样一次运行下来整个程序的执行轨迹就清清楚楚摆在眼前bug的位置往往一眼就能看出来。调试完记得把printf语句全部删掉或者用注释包起来。这个坑我在真实考场里踩过一次代码逻辑没问题但忘了删调试输出结果一直PR白白浪费了二十多分钟。5. 考场策略与心态管理最后再讲点考场上的实战经验。很多人平时刷题刷得飞起一到真实考场就状况百出这不是能力问题而是策略出了问题。5.1 拿到题目后的读题与拆解顺序上机考试一般有4到6道题时间大约3小时。拿到题目后我强烈建议先把所有题目快速浏览一遍标记出每道题的题型和数据规模。这一步只需要2-3分钟但能帮你建立起全局观哪些题是保险题一定拿分哪些题是挑战题可能拿部分分。做题顺序建议是“先易后难”。先把最有把握的题AC掉心里有底了再做难一点的题。千万不要一上来就死磕一道难题卡了一个小时最后0分心态直接爆炸。5.2 时间分配与检查清单一般分配原则是前30分钟用来吃透题目和解决两道简单题中间60-90分钟攻克中等难度题最后30分钟用来检查和提交。留出最后的缓冲时间非常重要因为总有各种意外情况出现。最后一轮检查时按这个清单逐项过一遍所有变量是否都正确初始化数组大小是否满足题目最大数据范围输出格式空格、换行、大小写是否完全一致是否有多余的调试输出没删掉复杂度的最坏情况是否能在1秒内跑完有没有申请大数组但没有释放导致的内存问题5.3 代码风格与命名规范考场上的代码不需要写得多么优雅但一定要清晰。变量名不要用a、b、c这种毫无信息量的命名也别为了秀操作写复杂的嵌套表达式。用有意义的单词命名比如head、prevNode、dp数组等最直接的好处是你在回看代码定位bug的时候不需要花时间去猜这个变量是干什么的。代码格式上循环体一定要打上花括号哪怕只有一行代码。这个习惯能避免很多“悬空else”和“循环只执行了一行”的经典低级错误。5.4 心态崩了怎么办上机考试的心态管理和算法能力同样重要。遇到一道题20分钟没有任何思路别硬抗果断跳过先做下一道。要知道复试上机的目标不是满分而是尽可能多拿分。保底题全AC顺利题拿分难题能暴力就暴力、能拿部分分就部分分这个策略远比死磕一道难题要合理。还有一点一旦连续提交失败就停下来离开代码深呼吸几次或者去喝口水。我见过太多考生在OJ前反复修改提交到整个人都懵了最后越改越错。其实90%的情况下答案就在你脑海里只是你被焦虑情绪裹挟住了暂时想不起来而已。冷静五分钟问题往往就解决了。说到底东华的复试OJ并不想刁难谁它只是用一套公平、客观的标准来检验你对数据结构与算法的真实掌握程度。把该打的基础打牢把经典的题型的解法吃透再配合实战的心态和策略通过它并不是什么遥不可及的事。希望这篇进阶篇4能给你带来一点帮助也祝正在备考的你一切顺利。