东华复试OJ刷题复盘：链表合并、括号匹配与最长上升子序列

复试上机刷题这件事走到第130题的时候我才真正感觉到“题感”开始成型。每天3题打卡看着简单难的是持续把每一题都嚼透。今天这篇复盘针对的是东华复试OJ上第130、131、132三道题合并两个有序链表、括号匹配、最长上升子序列。三道题分别落在链表、栈、动态规划三个高频考点上不算难但都有不少人容易翻车的细节值得完整梳理一遍。我说“值得复盘”不是客套话。刷题刷到这个阶段做题的目的早就不是“见过更多题”而是把已经见过的基础模型理解到足够深。130到132这一组题恰好是三种典型能力的试金石链表操作的边界处理能力、对“结构合法性”的判断敏感度、以及动态规划建模的基本功。下面按题目拆开讲给出完整代码也把做题时踩过的坑和测试用例一并放进来方便直接对照复习。1. 三道题复盘考点是什么为什么复试爱考1.1 130题合并两个有序链表这类题在各大OJ和面试题里都是熟面孔LeetCode 21、蓝桥杯、华为OD机考里都能见到原题或者变体。题目描述很直接输入两个按递增排列的链表合并成一个新的递增链表返回合并后的头结点。它不涉及高深算法考察的全是基本功指针怎么移动、边界条件怎么处理、代码能不能写干净。对机试来说这是筛人的第一道关卡。链表基本操作不熟的人大概率会在“头指针丢失”“空链表”这些细节上卡壳而写得顺的人通常还能顺手写出递归版本。我当时做这道题时脑子里最先过的是三个要素dummy头节点、判空、最后拼接剩余链表。这三个要素只要都在代码里出现基本就不会错。1.2 131题括号匹配题目回忆输入一个只包含括号字符的字符串判断括号是否合法。合法要求是每个左括号都能找到同类型的右括号且嵌套顺序正确。这是一道栈的入门题但“入门”不代表“没坑”。我见过很多人包括曾经的自己第一反应是用三个计数器统计左右括号数量最后判断数量是否相等。这种思路本地测几个普通例子会通过但提交OJ就是Wrong Answer。原因很简单计数器只记录数量不记录顺序。比如([)]这个字符串三种括号左右数量都各自相等但它是非法的。括号匹配之所以在复试上机里常出现是因为它在一小段代码里同时考察了字符串遍历、字符分类、基础数据结构运用、以及“逆序配对”这种结构思维的敏感度。而且它是后续表达式求值、逆波兰计算、甚至编译原理语法分析的思想基础属于性价比很高的一道经典题。1.3 132题最长上升子序列这道题从一个整数序列里求最长严格上升子序列的长度子序列不要求连续但必须保持原顺序。相比前两题它多了一个台阶需要动态规划建模能力。复试阶段的DP题一般不会刻意出到很难但很看重你能不能快速把状态方程写对。最标准的做法是dp[i]表示以第 i 个数字结尾的最长严格上升子序列长度。初始化时所有dp[i]都为1因为任何一个单独的数字都构成长度为1的子序列。转移方程是对每个 i遍历 j i如果nums[j] nums[i]就用dp[j] 1尝试更新dp[i]。如果数据规模大比如 n 到 10^5就要用 O(n log n) 的贪心加二分优化。复试题目如果只给到几百或一千的数据量O(n²) 也能过但两种写法都要掌握因为“会不会优化”有时就是区分水平的关键点。2. 解题思路演变从“会写”到“写对”2.1 链表合并迭代、递归和“别丢头”链表题最核心的一条原则头指针不能丢。很多新手在遍历时直接拿head head-next一路走下去最后想返回结果才发现头结点已经被甩到后面去了。解决这个问题最简单的武器就是dummy节点。所谓dummy就是先在堆栈或堆上创建一个值无意义的节点让它的next指向真正的头结点。这样无论后续链接多少个节点最终只要return dummy.next就能拿到完整链表头不需要单独处理“第一个节点是哪个”这种问题。迭代写法的思路是两个指针分别遍历两条链表谁的值小就把谁接在当前节点后面然后对应链表指针后移一位。循环直到某一条链表为空再把另一条剩余的链表直接接上。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ? l1 : l2; return dummy.next; }递归写法更短思路是每次在两条链表的头结点中选一个较小的并把它的next指向“剩余部分的合并结果”ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }我自己的习惯是OJ上默认写迭代法。原因有两个第一迭代法不需要递归栈链表特别长时也稳稳当当第二机试现场如果出了bug迭代版的变量状态更直观逐行调试更友好。递归写法理解为主能写出来是加分项。2.2 括号匹配从计数器到栈的思维升级先说说那个让我真实翻车的例子。早期我用三个变量分别记录小括号、中括号、大括号的数量遇左括号加一遇右括号减一最后判断三个计数器是否都为0。本地测()[]{}能过一提交就WA。我后来才彻底明白括号匹配要求的是“结构合法”不是“数量相等”。([)]这种交叉嵌套计数器算下来是对的结构却是错的。结构合法性怎么判断栈。左括号入栈右括号和栈顶比较。如果类型匹配弹出栈顶类型不匹配直接返回非法如果遇到右括号时栈是空的说明这个右括号没有对应的左括号也直接返回非法。遍历完整个字符串后栈必须为空否则说明有左括号没有被闭合。用上栈之后这类题基本就是套路了。而且括号匹配的栈思路可以迁移到不少场景表达式求值、标签配对、函数调用栈模拟本质上都是“后进的先闭合”这个逻辑。代码复盘放在第3节详细写这里只想强调一点遇右括号先判断栈是否为空这个顺序别反了。很多人WA就是栽在st.top()时栈里根本没元素直接越界或返回错误结果。2.3 LIS题O(n²)和O(n log n)分别怎么想O(n²) 的DP写法最直观也最好解释。对每个位置 i往前看所有位置 j只要nums[j] nums[i]就说明第 i 个数可以接到以第 j 个数结尾的上升子序列后面。这个思路就是典型的“从局部最优推导全局最优”。O(n log n) 的写法则换了一个角度维护一个数组tails其中tails[i]表示长度为 i1 的上升子序列的最小可能末尾值。遍历每个数 x在tails中找出第一个大于等于 x 的位置把它替换成 x如果找不到就把 x 追加到数组末尾。最终tails的长度就是最长上升子序列的长度。这个算法刚接触时容易被绕晕。关键理解点在于tails数组并不是真正的子序列它只记录“每种长度下末尾值能达到多小”。末尾值越小后续数字就越容易接上去从而有机会形成更长的子序列。每次替换不是在修改真实序列而是在压低“门槛”。复试时如果数据范围不大先写O(n²)版本保证正确性再根据情况挑优化版。但代码模板最好两个都背熟笔试选择题也偶尔会考复杂度。3. 上机实现细节与代码复盘3.1 东华OJ输入输出先搞定这些坑机试里真正让人丢分的往往不是算法而是输入输出。东华复试OJ这类平台有几个常见规矩第一多组数据输入。题面如果写“多组输入直到EOF”就必须把核心逻辑放在while (scanf(...) ! EOF)或while (cin n)循环里。有些同学只读一次就能过本地样例但OJ上会超时或答案错误。第二输出格式要抠字眼。链表输出时是“值之间用空格分隔末尾没有多余空格”还是“每个值后面都带空格”平台之间的习惯不一样。我处理的办法是盯着题目样例看样例里最后一个数字后面如果有空格就照抄没有就不加。打印代码建议先判断p-next是否存在再决定要不要打空格。第三链表题的输入可能是先给节点数量再给节点值也可能是用哨兵值结束。题目没看明白就动手写大概率白费时间。第四如果输入长度为0链表头指针就是空的合并时要注意对空链表的处理。这个在代码里就是if (!l1) return l2;这种一行判断但没有它后面所有操作都会崩。3.2 130题完整代码与链表构建核心合并代码已经写在2.1节了这里补充完整的输入构建和输出打印部分方便直接跑本地测试。#include cstdio struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* buildList() { int n; scanf(%d, n); ListNode* head nullptr; ListNode* tail nullptr; for (int i 0; i n; i) { int v; scanf(%d, v); ListNode* node new ListNode(v); if (head nullptr) { head tail node; } else { tail-next node; tail node; } } return head; } void printList(ListNode* head) { ListNode* p head; while (p) { printf(%d, p-val); if (p-next) printf( ); p p-next; } printf(\n); } int main() { ListNode* l1 buildList(); ListNode* l2 buildList(); ListNode* merged mergeTwoLists(l1, l2); printList(merged); return 0; }这段代码里最值得注意的其实是buildList里对头结点的特殊处理。第一次生成的节点既要当head也要当tail后面再生成的节点就只需要接在tail后面。这个模式在复试里经常用到链表题目无论如何变化构建链表这段代码都可以复用。调试中发现过一个隐蔽问题链表本地测试时偶尔莫名输出多一个0。排查后才知道是dummy(0)这个临时变量出了生命周期问题。如果dummy是局部变量而返回的指针指向的是dummy.next那没问题但如果返回的是dummy函数结束后就悬空了。写代码时一定要明确返回的是dummy.next不是dummy。3.3 131题完整代码与匹配逻辑误区#include iostream #include stack #include string using namespace std; bool isValid(const string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }这段代码的结构很清晰左括号直接入栈右括号先判空再比对类型。我在这个题上踩过的一个明显误区是只判断栈顶是不是对应的左括号却没有把三种情况统一处理。比如写成if (top () st.pop();然后漏掉中括号大括号或者用else直接不弹出最后答案必然出错。更聪明的做法是在遇到右括号时先构造“不匹配就返回false”的判断能走到st.pop()说明这一对括号已经正确配对。这样每种情况都覆盖到了代码也更好读。边界情况单独说一句空字符串在多数OJ里被视为合法括号序列直接输出true。遇到st.empty()却还有右括号的情况直接返回false不要等着最后再判断。3.4 132题完整代码与二分优化边界先写O(n²)版本这是最稳的复现方案。#include vector #include algorithm using namespace std; int lengthOfLIS(vectorint nums) { if (nums.empty()) return 0; vectorint dp(nums.size(), 1); int ans 1; for (int i 1; i nums.size(); i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }再写O(n log n)版本用lower_bound做二分替换。#include vector #include algorithm using namespace std; int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }这里有一个东华复试很爱考的分支题目要求“最长上升子序列”还是“最长非递减子序列”。如果是严格上升lower_bound找第一个不小于x的位置保证相同元素不会被算进上升序列如果是非递减相同元素可以连着算那就要用upper_bound找第一个大于x的位置。这个二分的边界细节就是很多人本地测没问题、提交却WA的原因。3.5 三道题测试用例与预期结果光有代码不够还得有可靠的测试用例。下面是我在做这三题时用的样例集基本上能覆盖到大多数边界题目测试输入期望输出说明130l1[1,2,4], l2[1,3,4][1,1,2,3,4,4]重复元素也要正常合并130l1[], l2[0][0]其中一条链表为空130l1[5], l2[1,2,3][1,2,3,5]一条整体比另一条大131()[]{}true三种括号合法嵌套131([)]false数量相等但结构非法131((false左括号未闭合131]false右括号没有对应左括号132[10,9,2,5,3,7,101,18]4经典LIS样例答案对应2,3,7,101132[7,7,7,7,7]1严格上升相同元素不能连用132[1,2,3,4,5]5全部递增132[]0空数组现场上机时我会先花三到五分钟把这组边界样例跑一遍再提交。别小看这个习惯它能发现大部分低级错误省下好几轮罚时。4. 每日3题打卡的复盘方法怎么把题榨干4.1 我每天的刷题节奏与时间分配刷到130题这个阶段我每天安排的时间大概是一个小时。分配方式很固定前五分钟读题不急着写代码先在草稿纸上画出输入输出格式和核心思路。二十分钟到三十分钟写代码并本地调试。这个环节最忌讳“边写边猜”一定要先理清状态转移或指针走向。剩下时间至少十分钟写复盘笔记。笔记不抄代码只记录三件事这道题的核心考点是什么、我卡在了哪一步、下次遇到同类型题目要注意什么。比如130题我卡在忘了处理空链表笔记里就写“链表题先判空尤其是合并和删除类操作”。131题卡在计数器思路笔记里写“括号、标签、嵌套结构一律先想栈”。这些一句话笔记比代码重要得多。4.2 三道题最常见的坑整理成速查表把三个题放在一起对比问题会更清晰题目典型坑应对口诀130 链表合并丢失头指针、没判空、最后接剩余时多写了循环建dummy先判空cur-next l1 ? l1 : l2131 括号匹配右括号时栈为空、类型错配、最后没判断栈空右括号先判空不匹配直接false结束时栈必须为空132 最长上升子序列dp初始化没全给1、严格上升写成非递减、二分边界用错dp初始为1严格上升用lower_bound非递减用upper_bound这三句话基本就是我复盘后沉淀下来的全部结论。复试题量不大每道题都经得起这种“提炼口诀”的压缩压缩到最后就变成考场上能快速调用的潜意识。4.3 打通的题感同类题怎么归类复盘最大的价值是把零散的题串成线。130到132这三道题分别能归到三条线里链表线合并有序链表、反转链表、删除倒数第N个节点、判断是否有环。这些题的核心技巧都是dummy头节点、快慢指针或者递归归到一起刷效率远高于乱序刷。栈线括号匹配、最小栈、逆波兰表达式求值。括号匹配是最基础的一环后两题基本是在此之上加一点规则。动态规划线最长上升子序列、最大连续子序列和、最长公共子序列。它们的共同套路是先定义dp[i]的含义再找转移方程最后初始化边界。状态定义想清楚三重这些题就是模板填空。每次复盘我都做这种“连接工作”不做的话刷题只是堆数量打通的才是题感。讲讲我做题之外的一点小经验。复试前的OJ打卡我给自己定的规矩不是“每天必须AC三题”而是“每天必须写三个题目的复盘”。有时候某道题实在没思路看答案看懂后第二天把代码关掉重写一遍这比死磕三小时更有用。复盘比刷题量重要这是刷到130题时我最大的体会。这三题复盘下来我自己印象最深的是131题。计数器思路看着省事却完全错失了“结构合法”这个本质换成栈之后代码量差不多却一下子把问题的核心拿住了。准备上机的同学如果时间有限建议优先把这种能迁移的经典模型吃透。后面我还有下一批题目要复盘到时候继续记录。