复试上机刷题这件事，走到第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]表示长度为 i+1 的上升子序列的最小可能末尾值。遍历每个数 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) { stack<char> 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(vector<int>& nums) { if (nums.empty()) return 0; vector<int> 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(vector<int>& nums) { vector<int> 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 三道题测试用例与预期结果
光有代码不够，还得有可靠的测试用例。下面是我在做这三题时用的样例集，基本上能覆盖到大多数边界：
| 题目 | 测试输入 | 期望输出 | 说明 |
|---|---|---|---|
| 130 | l1=[1,2,4], l2=[1,3,4] | [1,1,2,3,4,4] | 重复元素也要正常合并 |
| 130 | l1=[], l2=[0] | [0] | 其中一条链表为空 |
| 130 | l1=[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,101 |
| 132 | [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 : l2 |
| 131 括号匹配 | 右括号时栈为空、类型错配、最后没判断栈空 | 右括号先判空，不匹配直接false，结束时栈必须为空 |
| 132 最长上升子序列 | dp初始化没全给1、严格上升写成非递减、二分边界用错 | dp初始为1，严格上升用lower_bound，非递减用upper_bound |
这三句话基本就是我复盘后沉淀下来的全部结论。复试题量不大，每道题都经得起这种“提炼口诀”的压缩，压缩到最后就变成考场上能快速调用的潜意识。
4.3 打通的题感：同类题怎么归类
复盘最大的价值，是把零散的题串成线。130到132这三道题，分别能归到三条线里：
链表线：合并有序链表、反转链表、删除倒数第N个节点、判断是否有环。这些题的核心技巧都是dummy头节点、快慢指针或者递归，归到一起刷，效率远高于乱序刷。
栈线：括号匹配、最小栈、逆波兰表达式求值。括号匹配是最基础的一环，后两题基本是在此之上加一点规则。
动态规划线：最长上升子序列、最大连续子序列和、最长公共子序列。它们的共同套路是先定义dp[i]的含义，再找转移方程，最后初始化边界。状态定义想清楚，三重这些题就是模板填空。
每次复盘我都做这种“连接工作”，不做的话刷题只是堆数量，打通的才是题感。
讲讲我做题之外的一点小经验。复试前的OJ打卡，我给自己定的规矩不是“每天必须AC三题”，而是“每天必须写三个题目的复盘”。有时候某道题实在没思路，看答案看懂后，第二天把代码关掉重写一遍，这比死磕三小时更有用。复盘比刷题量重要，这是刷到130题时我最大的体会。
这三题复盘下来，我自己印象最深的是131题。计数器思路看着省事，却完全错失了“结构合法”这个本质；换成栈之后，代码量差不多，却一下子把问题的核心拿住了。准备上机的同学如果时间有限，建议优先把这种能迁移的经典模型吃透。后面我还有下一批题目要复盘，到时候继续记录。
