每年这个时候牛客网的模考系统一出来备战校招的群里就炸锅。尤其是“三模”这种接近正式难度的场次做完对答案、看解析、复盘错题基本成了很多人两周内的固定动作。我当年也是这么过来的2020年那场三模编程题我一共写了四道两道AC一道卡了半小时最后一道直接放弃。现在回头看这种“模考”真正的价值不在于分数而在于它把笔试中最容易出问题的几个环节——读题、复杂度估算、边界处理、调试节奏——全部压在一起让你提前练一遍。这篇文章就针对2020年牛客模考三模编程题集合做个深度复盘。我会把当年那批题目涉及的考点重新梳理一遍挑出几道当时考得最多、也最有代表性的题从读题到编码完整走一遍解题过程。文章里不会只贴代码还会把每道题背后的判断逻辑、易错点、复杂度权衡讲清楚。不管你是今年准备秋招的应届生还是刚刷题不久、想找找笔试节奏的学习者这篇复盘都可以直接拿来当参考。1. 模考内容设计三模编程题都在考什么1.1 从2020年校招笔试看牛客模考的定位牛客的模拟考试一般分好几场一摸二摸偏基础主要用来热身和查漏三模的定位通常是“贴近真实笔试”。2020年那会儿大厂校招在线笔试普遍用牛客系统所以三模的出题风格、难度曲线、时间限制都尽可能地往真实笔试靠。换句话说三模不是让你找成就感的而是让你提前感受“60分钟里既要写对、又要写完”是什么滋味。那一年我印象比较深的是编程题部分一共4道分值分布大概在20到30分不等总时长给到60到70分钟。前两道偏“模拟”和“字符串处理”第三道是“贪心区间”第四道开始上难度涉及动态规划。从题目分布能看出牛客出题人有个习惯前两道保基础后两道拉开区分度。如果你前三道都AC已经能干掉相当一部分人了。从复习角度看三模编程题集合其实是很好的“考点地图”。你不用去猜大厂出什么题只看模考里反复出现的题型就能摸出大概字符串、模拟、贪心、二分、简单DP这些是大头可能占到笔试编程题的七成以上。把这几类吃透笔试下限就有了。1.2 三模题目的三个典型特征复盘2020年三模以及往后几年我陆续看过的牛客模考编程题有几个很明显的共性特征第一题目描述“伪装”得很复杂。很多题会给你一段业务背景比如“小明在排队取餐”“系统需要分配服务器”剥掉壳子以后其实就是一个简单算法问题。这要求你不能被题干绕晕要能快速把业务语言翻译成数据结构。第二边界条件和数据范围非常抠门。字符串可能给到10^5长度数组可能要求输出时保持某种顺序不仔细读范围说明就容易写出一个看着对、提交就超时的解法。第三输入输出格式是硬规矩。笔试系统按严格格式匹配输出多打一个空格、少换一次行可能就判错。这不是你代码水平的问题是做题习惯的问题模考最擅长暴露这种问题。这些特征决定了复习策略刷题不是求“我会不会做”而是求“在有限时间内能不能做到完整、准确、优雅”。对着一道题耗一小时的钻研精神在校招笔试里没太大用。2. 高频考点拆解从基础到进阶的核心思路2.1 字符串处理类题目为何是必考项字符串问题在牛客笔试中出现频率极高原因很简单输入输出天然就是字符串处理字符、切分、匹配是计算机科学里最基础也最容易出变化的分支。2020年三模里有一道括号匹配相关的问题当时就考倒了一批人。以括号匹配为例最经典的解法是用栈。遇到左括号入栈遇到右括号出栈并做判断。很多新手都能说出这个思路但一写代码就出问题栈空了怎么办输入只有一个右括号是不是非法匹配结束后栈里还有东西是不是非法这些边界才是失分点。def is_valid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in pairs.values(): stack.append(ch) elif ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: return False return not stack这段代码的细节是右括号进来时先看栈里有没有左括号再看栈顶是否匹配两步缺一不可。最后返回时要判断栈是否为空避免漏掉多余左括号的情况。字符串类题目的核心不是背模板而是把“所有可能的非法情况”在动手前就列全写成自然的条件分支。2.2 模拟题的读题与状态建模模拟题在三模里也是常客这类题不考高深算法考的是“按照题目规则一步步实现”的耐心和精确度。2020年三模里有一道题是给一个二维网格按某种规则逐轮更新状态本质上就是模拟细胞自动机。很多同学一看到“二维”“逐轮更新”就发怵其实只要把状态转移写好别在循环里污染下一轮要用的数据就行。模拟题最忌讳的是“边算边改”。如果你在原数组上直接更新这一轮刚改好的值会被下一轮当作初始状态导致结果全乱。正确做法是复制一份旧状态新状态写到新数组等这一轮结束再整体替换。def next_state(grid): m, n len(grid), len(grid[0]) prev [row[:] for row in grid] new_grid [[0] * n for _ in range(m)] for i in range(m): for j in range(n): cnt count_neighbor(prev, i, j) if prev[i][j] 1 and cnt in (2, 3): new_grid[i][j] 1 elif prev[i][j] 0 and cnt 3: new_grid[i][j] 1 return new_grid处理这种题的时候先把“旧状态”和“新状态”从脑子里分开再动代码。状态建模清楚10分钟能写完建模混乱写两小时还在调“为什么结果多了一个活细胞”。2.3 贪心和二分的快速判断法则贪心算法和二分查找经常出现在三模的第三题、第四题位置。它们的特点是核心思路不难但你能不能快速识别出“这题就该用贪心”才是关键。我自己的判断法则很简单——题目说“要尽可能多/少”“求最大/最小结果”且每一步的局部最优选择不会影响之前的选择那多半就是贪心。区间合并问题是典型例子。给你一堆区间要求合并所有重叠区间输出合并后的区间数量。解法是先按起点排序然后逐个扫描维护当前合并区间的右端点。如果下一个区间的起点大于当前右端点说明没有重叠输出一个区间否则更新右端点为两者的较大值。intervals.sort(keylambda x: x[0]) merged [] for start, end in intervals: if not merged or start merged[-1][1]: merged.append([start, end]) else: merged[-1][1] max(merged[-1][1], end)这个解法的时间复杂度是O(n log n)主要是排序开销。很多人在这一步会犯一个思维错误试图在扫描过程中做更多事比如存储所有合并结果。其实题目只要求数量就只维护一个右端点变量即可别给自己加戏。2.4 动态规划题的暴力转优化思路第四题涉及动态规划时很多人的第一反应是恐惧。但2020年三模的DP题并不是那种需要很高天赋的“难题”它更像是“从暴力递归到记忆化再到递推”的标准演化问题看你能不能识别出重叠子问题。以最长上升子序列LIS为例。最暴力的做法是枚举所有子序列复杂度是O(2^n)直接人没了。接着想到用DPdp[i]表示以第i个元素结尾的最长上升子序列长度转移时往前找所有比当前元素小的jdp[i] max(dp[j]) 1复杂度O(n^2)。n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这段代码能过但如果你看数据范围是n10^5O(n^2)就超时了。这时候需要用二分优化维护一个数组tailstails[k]表示长度为k1的上升子序列的末尾元素最小值每次用bisect_left找到当前元素应该替换的位置。很多人在这一步卡住是因为不理解“最小末尾值”这个设计意图。其实它的逻辑是同样长度的上升子序列结尾越小越容易在后面接上新元素所以我们要贪心地维护更小的结尾。import bisect tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这就是从暴力到优化的一条完整路径。笔试中出现DP题除非数据范围很小否则基本都在考察“你能不能从零开始推导出优化解法”而不是考察你背多少模板。3. 实战复盘四道典型题目的完整解题流程3.1 第一题括号匹配变形——求最长有效括号长度2020年三模第一道编程题在我看来是全场最“心机”的基础题。它没有让你直接判断括号是否合法而是给一串由左右括号组成的字符串求最长有效括号子串的长度。刷过LeetCode的人看到这题都会熟悉知道这题有栈解法和DP解法但在一小时内能把边界处理对的中等生并不多。栈解法的核心思路是在栈底留一个“锚点”记录当前未匹配的最右位置。遇到左括号就入栈其索引遇到右括号则先出栈如果栈为空说明当前右括号没有匹配的左括号把它当作新的锚点压栈否则有效长度为当前索引减去新的栈顶。def longest_valid_parentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans这里最重要的细节是初始把-1压入栈以及右括号导致栈空后把当前索引压入栈作为新锚点。这两个操作对应了“连续有效段从哪里开始算”的问题。我在考场上第一次写这题时忘了处理栈空的情况结果遇到“)(”这种输入答案是错的。经验是括号类题目凡是涉及“最长”“连续”都要在纸上先跑几个像)()())、()(()这样的反例再动键盘。3.2 第二题二维矩阵中最大全1正方形的面积第二题是一道经典的动态规划题在2020年三模里被包装成了“寻找最大海报面积”的场景。题目给一个由0和1组成的二维矩阵求只包含1的最大正方形的面积。这题在牛客出现频率极高属于“笔试基本功”。状态定义是dp[i][j]表示以(i,j)为右下角的最大全1正方形的边长。如果matrix[i][j]等于1那么dp[i][j]由左上、上、左三个位置的dp值中的最小值加上1得到。否则dp[i][j]等于0。这个递推公式想通了之后整个题目就没有难点。def maximal_square(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) dp [[0] * n for _ in range(m)] max_side 0 for i in range(m): for j in range(n): if matrix[i][j] 1: if i 0 or j 0: dp[i][j] 1 else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 max_side max(max_side, dp[i][j]) return max_side * max_side考场上容易被卡的地方是边界条件。i0或j0时dp值只能取1因为没法往左上扩展。很多人在初始化时把整行整列先填好再循环内部这当然可以但不如上面这种统一判断来得干净。另一个小坑是在牛客的Python输入里matrix的元素可能是字符串1而不是整数1判断时不要写错。3.3 第三题区间合并的在线筛选问题第三题是区间合并的变体给出一堆时间区间要求删除最少区间使得剩余区间互不重叠。这题在LeetCode上是“Non-overlapping Intervals”牛客模考很喜欢把它做成“会议安排”场景。解题关键其实在贪心策略按区间终点排序优先保留终点早的区间这样能给后续区间留出更多空间。很多人会想当然按起点排序然后逐个判断重叠。但按起点排序在某些用例下会错。比如区间[1,4]、[2,3]、[3,5]按起点排序后1和4重叠2和3重叠逻辑容易乱按终点排序[2,3]最早结束保留它然后跳过[1,4]再保留[3,5]得到最优解。def erase_overlap_intervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) ans 0 last_end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] last_end: ans 1 else: last_end intervals[i][1] return ans这道题给我们的教训是贪心策略的选择不能凭感觉要举反例验证。如果你拿几组数据在纸上画一画终点排序的合理性会非常直观。我在笔试时吃过一次亏后养成了个习惯——写贪心前先试图构造一个反例证明自己的策略是错的如果构造不出来再写代码。3.4 第四题最长上升子序列的“友好”变体第四题给了个数组问最少分成几组每组内部保持严格递增。这题猛地一看像在考贪心实际上是最长上升子序列题型的换皮。把数组分成若干严格递增的子序列等价于求“最少的不上升子序列覆盖数”根据 Dilworth 定理它等于最长下降子序列的长度。放到代码层面和前面说的bisect求LIS几乎一样只是把比较方向反过来。我当时在考场上没想起来这层转化直接暴力回溯结果只过了一半用例。复盘时才发现这道题只要把数组顺序反过来想或者把tails数组的更新条件改成“找到第一个大于等于当前元素的位置”就能在O(n log n)时间内解决。它算不上难题但考察的是你对经典题型的迁移能力。import bisect def min_groups(arr): tails [] for x in arr: pos bisect.bisect_right(tails, x) # 非严格递减的覆盖 if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这种“换皮题”在牛客模考里很常见。应对方法就是平时刷题不要只满足于AC要把题目的本质抽象出来比如“这题其实就是在求LIS”“这题其实就是区间贪心”这样上了考场遇到再花哨的包装也能一眼看穿内核。4. 高频错误与排查技巧笔试现场的真实教训4.1 自查清单为什么你本地跑得好好的提交就挂我在2020年三模和后来的正式笔试里踩过最多的坑不是算法不会而是提交后判错。事后复盘主要问题集中在几个方面输入格式没按系统要求处理、变量名污染导致多组数据间状态残留、输出时多了多余空格或换行。这里给你一份我在刷题后期固定使用的自查清单每次提交前花30秒过一遍输入是用input()还是sys.stdin.readline()如果数据量大后者更稳能避免读入超时。多组测试数据时循环里用的全局变量有没有重置列表、计数器的初始状态必须放在循环内。输出格式是“每个结果占一行”还是“以空格分隔”最后一行的结尾是否允许多余空格数据范围是多少如果n超过10^5O(n^2)的解法基本必挂。字符串里的字符是大写还是小写数字是int还是str判断条件里类型写混了会非常隐蔽地出错。别看这些问题简单几乎每次模考都会有人因为这些丢分。尤其是输入输出在牛客系统里哪怕多打一个空格测评结果都会是“格式错误”而不是“答案错误”。4.2 60分钟编程题的实战时间分配三模的编程题总时长大概在60到70分钟我见过不少人在第一题就耗了半小时结果后面三题全崩。后来我摸索出一套适合自己的时间分配策略也分享过给几个学弟学妹反馈都还不错。拿到题目先不急着写花2到3分钟把四道题都扫一遍。第一眼判断每道题的类型和大致难度心里给它们排个序从最简单、最熟悉、最可能AC的开始写。如果一道题想了10分钟还是没有清晰的思路立刻跳过做下一题不要恋战。所有题都做一遍之后再回来死磕卡住的那道。这样安排能保证你先拿到该拿的分而不是在一道题上赌运气。每次写完一道题不管多自信都留出1到2分钟自己构造两组测试用例一组常规数据一组边界数据。边界数据包括空输入、只有一个元素、全是相同元素、最大数值范围。花这点时间至少能救回一道题的10%用例。4.3 从模考分数反推复习重点模考最大的价值不是那个分数而是分数背后的“失分结构”。我建议你每次模考后不要只盯着总分而是把错题按原因分成三类第一类是“算法不会”比如动态规划压根想不到状态转移第二类是“思路对但实现有bug”比如边界条件写错第三类是“粗心丢分”比如输出格式不对、变量名敲错。如果是第一类问题就需要回头补对应的专题比如把LIS、背包、区间DP各刷五到十道经典题形成肌肉记忆。如果是第二类问题说明代码功底还不够扎实平时刷题时不仅要追求AC还要刻意练习“手动构造反例”和“代码走读”这两项能力。如果是第三类问题没有别的办法多模考几场把自己训练成“提交前检查清单机器”。2020年三模之后我正式笔试前又做了两套模拟题每次都按这个复盘流程走。等到真实笔试时基本上看到题目就能条件反射式地判断考点、设计解法、检查边界。这种“题感”不是靠天赋是靠一次次实打实的模拟训练磨出来的。5. 写在最后的几点个人心得复盘2020年牛客三模这组编程题我发现一个很有意思的现象真正拉开差距的往往不是最后那道难题而是前面几道“看起来简单”的基础题。第二题的dp边界、第三题的排序策略、第四题的题型迁移每一处都是可以靠刻意练习补上的短板。那些能在牛客模考里稳定拿高分的同学通常不是算法天才而是流程化做题做到极致的普通人。最后分享一个小技巧。你刷完一套模考题之后把每道题的题号、考点、错误原因记录在一个表格里。坚持记录五套你就能看到自己的薄弱点集中在哪个专题。这个表格比任何网课都值钱因为它是完全针对你个人的失分地图。别嫌麻烦这一套流程走下来你校招笔试的稳定性会肉眼可见地提升。
每年这个时候牛客网的模考系统一出来备战校招的群里就炸锅。尤其是“三模”这种接近正式难度的场次做完对答案、看解析、复盘错题基本成了很多人两周内的固定动作。我当年也是这么过来的2020年那场三模编程题我一共写了四道两道AC一道卡了半小时最后一道直接放弃。现在回头看这种“模考”真正的价值不在于分数而在于它把笔试中最容易出问题的几个环节——读题、复杂度估算、边界处理、调试节奏——全部压在一起让你提前练一遍。这篇文章就针对2020年牛客模考三模编程题集合做个深度复盘。我会把当年那批题目涉及的考点重新梳理一遍挑出几道当时考得最多、也最有代表性的题从读题到编码完整走一遍解题过程。文章里不会只贴代码还会把每道题背后的判断逻辑、易错点、复杂度权衡讲清楚。不管你是今年准备秋招的应届生还是刚刷题不久、想找找笔试节奏的学习者这篇复盘都可以直接拿来当参考。1. 模考内容设计三模编程题都在考什么1.1 从2020年校招笔试看牛客模考的定位牛客的模拟考试一般分好几场一摸二摸偏基础主要用来热身和查漏三模的定位通常是“贴近真实笔试”。2020年那会儿大厂校招在线笔试普遍用牛客系统所以三模的出题风格、难度曲线、时间限制都尽可能地往真实笔试靠。换句话说三模不是让你找成就感的而是让你提前感受“60分钟里既要写对、又要写完”是什么滋味。那一年我印象比较深的是编程题部分一共4道分值分布大概在20到30分不等总时长给到60到70分钟。前两道偏“模拟”和“字符串处理”第三道是“贪心区间”第四道开始上难度涉及动态规划。从题目分布能看出牛客出题人有个习惯前两道保基础后两道拉开区分度。如果你前三道都AC已经能干掉相当一部分人了。从复习角度看三模编程题集合其实是很好的“考点地图”。你不用去猜大厂出什么题只看模考里反复出现的题型就能摸出大概字符串、模拟、贪心、二分、简单DP这些是大头可能占到笔试编程题的七成以上。把这几类吃透笔试下限就有了。1.2 三模题目的三个典型特征复盘2020年三模以及往后几年我陆续看过的牛客模考编程题有几个很明显的共性特征第一题目描述“伪装”得很复杂。很多题会给你一段业务背景比如“小明在排队取餐”“系统需要分配服务器”剥掉壳子以后其实就是一个简单算法问题。这要求你不能被题干绕晕要能快速把业务语言翻译成数据结构。第二边界条件和数据范围非常抠门。字符串可能给到10^5长度数组可能要求输出时保持某种顺序不仔细读范围说明就容易写出一个看着对、提交就超时的解法。第三输入输出格式是硬规矩。笔试系统按严格格式匹配输出多打一个空格、少换一次行可能就判错。这不是你代码水平的问题是做题习惯的问题模考最擅长暴露这种问题。这些特征决定了复习策略刷题不是求“我会不会做”而是求“在有限时间内能不能做到完整、准确、优雅”。对着一道题耗一小时的钻研精神在校招笔试里没太大用。2. 高频考点拆解从基础到进阶的核心思路2.1 字符串处理类题目为何是必考项字符串问题在牛客笔试中出现频率极高原因很简单输入输出天然就是字符串处理字符、切分、匹配是计算机科学里最基础也最容易出变化的分支。2020年三模里有一道括号匹配相关的问题当时就考倒了一批人。以括号匹配为例最经典的解法是用栈。遇到左括号入栈遇到右括号出栈并做判断。很多新手都能说出这个思路但一写代码就出问题栈空了怎么办输入只有一个右括号是不是非法匹配结束后栈里还有东西是不是非法这些边界才是失分点。def is_valid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in pairs.values(): stack.append(ch) elif ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: return False return not stack这段代码的细节是右括号进来时先看栈里有没有左括号再看栈顶是否匹配两步缺一不可。最后返回时要判断栈是否为空避免漏掉多余左括号的情况。字符串类题目的核心不是背模板而是把“所有可能的非法情况”在动手前就列全写成自然的条件分支。2.2 模拟题的读题与状态建模模拟题在三模里也是常客这类题不考高深算法考的是“按照题目规则一步步实现”的耐心和精确度。2020年三模里有一道题是给一个二维网格按某种规则逐轮更新状态本质上就是模拟细胞自动机。很多同学一看到“二维”“逐轮更新”就发怵其实只要把状态转移写好别在循环里污染下一轮要用的数据就行。模拟题最忌讳的是“边算边改”。如果你在原数组上直接更新这一轮刚改好的值会被下一轮当作初始状态导致结果全乱。正确做法是复制一份旧状态新状态写到新数组等这一轮结束再整体替换。def next_state(grid): m, n len(grid), len(grid[0]) prev [row[:] for row in grid] new_grid [[0] * n for _ in range(m)] for i in range(m): for j in range(n): cnt count_neighbor(prev, i, j) if prev[i][j] 1 and cnt in (2, 3): new_grid[i][j] 1 elif prev[i][j] 0 and cnt 3: new_grid[i][j] 1 return new_grid处理这种题的时候先把“旧状态”和“新状态”从脑子里分开再动代码。状态建模清楚10分钟能写完建模混乱写两小时还在调“为什么结果多了一个活细胞”。2.3 贪心和二分的快速判断法则贪心算法和二分查找经常出现在三模的第三题、第四题位置。它们的特点是核心思路不难但你能不能快速识别出“这题就该用贪心”才是关键。我自己的判断法则很简单——题目说“要尽可能多/少”“求最大/最小结果”且每一步的局部最优选择不会影响之前的选择那多半就是贪心。区间合并问题是典型例子。给你一堆区间要求合并所有重叠区间输出合并后的区间数量。解法是先按起点排序然后逐个扫描维护当前合并区间的右端点。如果下一个区间的起点大于当前右端点说明没有重叠输出一个区间否则更新右端点为两者的较大值。intervals.sort(keylambda x: x[0]) merged [] for start, end in intervals: if not merged or start merged[-1][1]: merged.append([start, end]) else: merged[-1][1] max(merged[-1][1], end)这个解法的时间复杂度是O(n log n)主要是排序开销。很多人在这一步会犯一个思维错误试图在扫描过程中做更多事比如存储所有合并结果。其实题目只要求数量就只维护一个右端点变量即可别给自己加戏。2.4 动态规划题的暴力转优化思路第四题涉及动态规划时很多人的第一反应是恐惧。但2020年三模的DP题并不是那种需要很高天赋的“难题”它更像是“从暴力递归到记忆化再到递推”的标准演化问题看你能不能识别出重叠子问题。以最长上升子序列LIS为例。最暴力的做法是枚举所有子序列复杂度是O(2^n)直接人没了。接着想到用DPdp[i]表示以第i个元素结尾的最长上升子序列长度转移时往前找所有比当前元素小的jdp[i] max(dp[j]) 1复杂度O(n^2)。n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这段代码能过但如果你看数据范围是n10^5O(n^2)就超时了。这时候需要用二分优化维护一个数组tailstails[k]表示长度为k1的上升子序列的末尾元素最小值每次用bisect_left找到当前元素应该替换的位置。很多人在这一步卡住是因为不理解“最小末尾值”这个设计意图。其实它的逻辑是同样长度的上升子序列结尾越小越容易在后面接上新元素所以我们要贪心地维护更小的结尾。import bisect tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这就是从暴力到优化的一条完整路径。笔试中出现DP题除非数据范围很小否则基本都在考察“你能不能从零开始推导出优化解法”而不是考察你背多少模板。3. 实战复盘四道典型题目的完整解题流程3.1 第一题括号匹配变形——求最长有效括号长度2020年三模第一道编程题在我看来是全场最“心机”的基础题。它没有让你直接判断括号是否合法而是给一串由左右括号组成的字符串求最长有效括号子串的长度。刷过LeetCode的人看到这题都会熟悉知道这题有栈解法和DP解法但在一小时内能把边界处理对的中等生并不多。栈解法的核心思路是在栈底留一个“锚点”记录当前未匹配的最右位置。遇到左括号就入栈其索引遇到右括号则先出栈如果栈为空说明当前右括号没有匹配的左括号把它当作新的锚点压栈否则有效长度为当前索引减去新的栈顶。def longest_valid_parentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans这里最重要的细节是初始把-1压入栈以及右括号导致栈空后把当前索引压入栈作为新锚点。这两个操作对应了“连续有效段从哪里开始算”的问题。我在考场上第一次写这题时忘了处理栈空的情况结果遇到“)(”这种输入答案是错的。经验是括号类题目凡是涉及“最长”“连续”都要在纸上先跑几个像)()())、()(()这样的反例再动键盘。3.2 第二题二维矩阵中最大全1正方形的面积第二题是一道经典的动态规划题在2020年三模里被包装成了“寻找最大海报面积”的场景。题目给一个由0和1组成的二维矩阵求只包含1的最大正方形的面积。这题在牛客出现频率极高属于“笔试基本功”。状态定义是dp[i][j]表示以(i,j)为右下角的最大全1正方形的边长。如果matrix[i][j]等于1那么dp[i][j]由左上、上、左三个位置的dp值中的最小值加上1得到。否则dp[i][j]等于0。这个递推公式想通了之后整个题目就没有难点。def maximal_square(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) dp [[0] * n for _ in range(m)] max_side 0 for i in range(m): for j in range(n): if matrix[i][j] 1: if i 0 or j 0: dp[i][j] 1 else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 max_side max(max_side, dp[i][j]) return max_side * max_side考场上容易被卡的地方是边界条件。i0或j0时dp值只能取1因为没法往左上扩展。很多人在初始化时把整行整列先填好再循环内部这当然可以但不如上面这种统一判断来得干净。另一个小坑是在牛客的Python输入里matrix的元素可能是字符串1而不是整数1判断时不要写错。3.3 第三题区间合并的在线筛选问题第三题是区间合并的变体给出一堆时间区间要求删除最少区间使得剩余区间互不重叠。这题在LeetCode上是“Non-overlapping Intervals”牛客模考很喜欢把它做成“会议安排”场景。解题关键其实在贪心策略按区间终点排序优先保留终点早的区间这样能给后续区间留出更多空间。很多人会想当然按起点排序然后逐个判断重叠。但按起点排序在某些用例下会错。比如区间[1,4]、[2,3]、[3,5]按起点排序后1和4重叠2和3重叠逻辑容易乱按终点排序[2,3]最早结束保留它然后跳过[1,4]再保留[3,5]得到最优解。def erase_overlap_intervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) ans 0 last_end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] last_end: ans 1 else: last_end intervals[i][1] return ans这道题给我们的教训是贪心策略的选择不能凭感觉要举反例验证。如果你拿几组数据在纸上画一画终点排序的合理性会非常直观。我在笔试时吃过一次亏后养成了个习惯——写贪心前先试图构造一个反例证明自己的策略是错的如果构造不出来再写代码。3.4 第四题最长上升子序列的“友好”变体第四题给了个数组问最少分成几组每组内部保持严格递增。这题猛地一看像在考贪心实际上是最长上升子序列题型的换皮。把数组分成若干严格递增的子序列等价于求“最少的不上升子序列覆盖数”根据 Dilworth 定理它等于最长下降子序列的长度。放到代码层面和前面说的bisect求LIS几乎一样只是把比较方向反过来。我当时在考场上没想起来这层转化直接暴力回溯结果只过了一半用例。复盘时才发现这道题只要把数组顺序反过来想或者把tails数组的更新条件改成“找到第一个大于等于当前元素的位置”就能在O(n log n)时间内解决。它算不上难题但考察的是你对经典题型的迁移能力。import bisect def min_groups(arr): tails [] for x in arr: pos bisect.bisect_right(tails, x) # 非严格递减的覆盖 if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这种“换皮题”在牛客模考里很常见。应对方法就是平时刷题不要只满足于AC要把题目的本质抽象出来比如“这题其实就是在求LIS”“这题其实就是区间贪心”这样上了考场遇到再花哨的包装也能一眼看穿内核。4. 高频错误与排查技巧笔试现场的真实教训4.1 自查清单为什么你本地跑得好好的提交就挂我在2020年三模和后来的正式笔试里踩过最多的坑不是算法不会而是提交后判错。事后复盘主要问题集中在几个方面输入格式没按系统要求处理、变量名污染导致多组数据间状态残留、输出时多了多余空格或换行。这里给你一份我在刷题后期固定使用的自查清单每次提交前花30秒过一遍输入是用input()还是sys.stdin.readline()如果数据量大后者更稳能避免读入超时。多组测试数据时循环里用的全局变量有没有重置列表、计数器的初始状态必须放在循环内。输出格式是“每个结果占一行”还是“以空格分隔”最后一行的结尾是否允许多余空格数据范围是多少如果n超过10^5O(n^2)的解法基本必挂。字符串里的字符是大写还是小写数字是int还是str判断条件里类型写混了会非常隐蔽地出错。别看这些问题简单几乎每次模考都会有人因为这些丢分。尤其是输入输出在牛客系统里哪怕多打一个空格测评结果都会是“格式错误”而不是“答案错误”。4.2 60分钟编程题的实战时间分配三模的编程题总时长大概在60到70分钟我见过不少人在第一题就耗了半小时结果后面三题全崩。后来我摸索出一套适合自己的时间分配策略也分享过给几个学弟学妹反馈都还不错。拿到题目先不急着写花2到3分钟把四道题都扫一遍。第一眼判断每道题的类型和大致难度心里给它们排个序从最简单、最熟悉、最可能AC的开始写。如果一道题想了10分钟还是没有清晰的思路立刻跳过做下一题不要恋战。所有题都做一遍之后再回来死磕卡住的那道。这样安排能保证你先拿到该拿的分而不是在一道题上赌运气。每次写完一道题不管多自信都留出1到2分钟自己构造两组测试用例一组常规数据一组边界数据。边界数据包括空输入、只有一个元素、全是相同元素、最大数值范围。花这点时间至少能救回一道题的10%用例。4.3 从模考分数反推复习重点模考最大的价值不是那个分数而是分数背后的“失分结构”。我建议你每次模考后不要只盯着总分而是把错题按原因分成三类第一类是“算法不会”比如动态规划压根想不到状态转移第二类是“思路对但实现有bug”比如边界条件写错第三类是“粗心丢分”比如输出格式不对、变量名敲错。如果是第一类问题就需要回头补对应的专题比如把LIS、背包、区间DP各刷五到十道经典题形成肌肉记忆。如果是第二类问题说明代码功底还不够扎实平时刷题时不仅要追求AC还要刻意练习“手动构造反例”和“代码走读”这两项能力。如果是第三类问题没有别的办法多模考几场把自己训练成“提交前检查清单机器”。2020年三模之后我正式笔试前又做了两套模拟题每次都按这个复盘流程走。等到真实笔试时基本上看到题目就能条件反射式地判断考点、设计解法、检查边界。这种“题感”不是靠天赋是靠一次次实打实的模拟训练磨出来的。5. 写在最后的几点个人心得复盘2020年牛客三模这组编程题我发现一个很有意思的现象真正拉开差距的往往不是最后那道难题而是前面几道“看起来简单”的基础题。第二题的dp边界、第三题的排序策略、第四题的题型迁移每一处都是可以靠刻意练习补上的短板。那些能在牛客模考里稳定拿高分的同学通常不是算法天才而是流程化做题做到极致的普通人。最后分享一个小技巧。你刷完一套模考题之后把每道题的题号、考点、错误原因记录在一个表格里。坚持记录五套你就能看到自己的薄弱点集中在哪个专题。这个表格比任何网课都值钱因为它是完全针对你个人的失分地图。别嫌麻烦这一套流程走下来你校招笔试的稳定性会肉眼可见地提升。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
