牛客三模编程题精讲：边界处理与解题节奏实战

2020年牛客模考三模的这套编程题我前前后后刷了三遍每次都有新收获。今天把里面几道值得反复做的题拆开揉碎讲一遍包括我自己踩过的坑和后来总结出来的解题节奏。如果你正准备春招秋招的在线笔试或者刚开始刷OJ想练基本功这套题是很合适的试金石——它不考偏题怪题考的就是代码功底、边界处理和调试能力。先给个总体评价这套题的难度曲线是缓坡上升的前几道基本是送分题但送分里藏着细节比如输入格式、边界条件稍不留神就WA。后面几道开始考察对数据结构的理解用栈、用双指针、用排序规则都属于“基础算法”范畴。整体来说它和很多大厂笔试的出题风格很接近这也是我反复刷它的原因。1. 内容整体设计与思路拆解1.1 这套题到底在考什么从题目分布来看三模编程题主要覆盖了四类模拟题、字符串处理、数组操作、经典数据结构应用。模拟题考的是能不能把题目描述翻译成代码字符串题考的是细节处理数组题考的是逻辑清晰度数据结构题考的是基础是否扎实。你可能会觉得这些太基础了但实际面试笔试中挂人的往往不是难题而是这些基础题。牛客的判题系统对输出格式要求非常严格多一个空格、少一个换行都可能判WA这种“非技术性失败”才是最可惜的。这套题恰好能训练你对这类细节的敏感度。1.2 为什么三模值得反复刷我个人的体会是模考题比市面上很多“偏难怪”题库更接近真实笔试环境。真实笔试时间紧、题量适中、难度呈梯度分布三模就很符合这个特征。它不像有些练习题库那样故意堆砌冷门算法也不像竞赛题那样需要大量数学推导。另外同类型的题目在不同年份的三模中反复出现比如字符串循环移位2020年考了换个包装2021年又考了。刷三模的意义就在于你把高频的题型套路吃透了再遇到同类题就能快速识别考点直接套用熟悉的解法框架省去大量现场思考时间。2. 核心题目逐个拆解2.1 成绩统计模拟题里的排序陷阱这道题在笔试中出现频率极高基本属于必会题。题目大意是输入n个学生的姓名和三科成绩按总分从高到低排序总分相同按语文成绩从高到低排序语文也相同则按输入顺序输出。拿到题先别急着写排序先理清楚排序规则是几级排序。这里其实是三个关键字总分降序、语文降序、输入顺序升序。很多人只写了前两个条件第三个“输入顺序”直接忽略了。由于排序算法是不稳定的忽略了它可能在部分测试用例下出错。import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) idx 1 students [] for i in range(n): name data[idx] idx 1 a int(data[idx]) b int(data[idx 1]) c int(data[idx 2]) idx 3 total a b c students.append((total, a, i, name)) students.sort(keylambda x: (-x[0], -x[1], x[2])) for total, a, i, name in students: print(name, total) if __name__ __main__: main()这里的核心是我用i记录了输入顺序并在元组中作为第三关键字。-x[0]和-x[1]实现降序x[2]实现升序。有些同学会用sorted(..., reverseTrue)但reverseTrue会把所有关键字都倒过来导致输入顺序也变成逆序反而不对。所以最稳妥的方式就是lambda里显式指出每个关键字的排序方向。还有一个容易踩的坑sys.stdin.read()读到的数据末尾可能有换行用strip()处理一下。如果只写split()其实也能处理空白符但养成strip()的习惯可以避免一些诡异问题。这道题的时间复杂度是O(n log n)主要开销在排序上。n在10^4量级以内都没问题。如果n到了10^6可能要考虑用计数排序思路但笔试一般不会卡这么死。2.2 字符串循环右移取模运算的妙用字符串循环移位是另一个高频考点。题目描述给定字符串s和非负整数k把s循环右移k位例如abcde右移2位得到deabc。注意k的范围可能很大题目没明说的时候也要有意识地对k取模。为什么要取模因为右移len(s)位等于没移所以k的有效范围是[0, len(s)-1]。如果不取模k10^9时切片操作会越界或者得到错误结果。s input().strip() k int(input()) if not s: print() else: k % len(s) if k 0: print(s) else: print(s[-k:] s[:-k])这里有几个边界情况要特别留意。第一字符串为空时直接输出空行很多人会忽略这个判断导致运行时错误。第二k0时虽然s[-0:] s[:-0]等价于s s[:0]结果碰巧正确但逻辑上不好看而且容易隐藏问题不如显式判断。第三输入里的字符串可能有前导或尾随空格用strip()去掉。还有一个细节如果题目要求的是循环左移只需要改成s[k:] s[:k]逻辑一脉相承。这种题我建议在本地IDE里多测几组数据空串、k0、k等于字符串长度、k大于字符串长度、k是len(s)的整数倍。把这几个case测完基本不会翻车。2.3 矩阵翻转先水平还是先垂直矩阵翻转题看起来简单但稍不注意就会把行和列搞反。题目要求先水平翻转左右翻转再垂直翻转上下翻转。输入一个n行m列的矩阵输出翻转后的结果。所谓水平翻转就是每一行的元素逆序垂直翻转就是把整个数组上下颠倒。先水平再垂直其实等价于把矩阵旋转180度。这个等价关系能帮你快速验证代码是否正确。n, m map(int, input().split()) a [list(map(int, input().split())) for _ in range(n)] for i in range(n - 1, -1, -1): print( .join(map(str, a[i][::-1])))这段代码的思路是从最后一行往上遍历同时把当前行用[::-1]逆序输出。这样一步就同时完成了垂直翻转和水平翻转。如果你非要按题目描述分两步做也可以先每行逆序再把整个数组倒过来结果一样。我见过不少同学在这里犯的错是把n和m搞混或者range(n - 1, -1, -1)写成了range(n, 0, -1)导致第一行没有被输出。这个边界值必须自己心里有数range(n - 1, -1, -1)里的第二个参数是-1表示取到0如果写成0就漏掉索引0那一行。另外输出格式要求每行元素用空格分隔行末不能有多余空格。 .join(...)正好满足别用print(*row)因为*展开在某些平台输出会有格式问题。2.4 括号匹配栈的经典应用括号匹配是数据结构基础题也是栈这个结构最经典的入门场景。题目要求判断一个只包含()[]{}的字符串是否合法合法条件是左右括号一一对应且嵌套顺序正确。这道题考的不是会不会用栈而是对“匹配规则”的理解。遇到左括号入栈遇到右括号时看栈顶是否是对应的左括号是则弹出不是则失败。最后还要检查栈是否为空因为可能右括号都匹配完了但还有多余的左括号。s input().strip() pairs {): (, ]: [, }: {} stack [] ok True for ch in s: if ch in ([{: stack.append(ch) else: if not stack or stack[-1] ! pairs[ch]: ok False break stack.pop() if ok and not stack: print(true) else: print(false)这段代码简洁但有几个地方需要解释。pairs这个字典的key是右括号value是对应的左括号这样在遇到右括号时可以直接stack[-1] ! pairs[ch]判断是否匹配不需要写一堆elif。这是一个很实用的编码小技巧。我踩过的坑是判断stack是否为空放在stack[-1]之后。如果栈为空还取stack[-1]会直接抛IndexError运行时错误比WA更难看。所以必须用not stack or把空栈判断放在前面Python的短路求值保证不会访问不存在的元素。3. 机考环境下的实战策略3.1 读题时先把关键条件圈出来很多WA不是不会做是没看清题目。我总结了一个读题的固定流程先看数据范围再看输入输出格式最后看算法要求。数据范围能帮你估算复杂度上限输入输出格式决定了你的代码怎么读数据、怎么输出结果算法要求决定了能不能用暴力解法。比如上面说的字符串循环右移如果题目明确k ≤ 10^9你第一时间就应该意识到要取模而不是傻傻地循环k次。再比如矩阵翻转如果n和m最大是1000暴力开辟新矩阵也完全没问题但如果你能原地操作空间复杂度就是O(1)这也是加分项。3.2 调试不要靠猜用样例反推在牛客上做题最快的调试方式就是拿题目给的样例跑一遍看输出对不对。如果对了但提交WA多半是边界问题这时候自己构造几组特殊数据空输入、单元素输入、最大数据范围输入、重复元素输入。我之前调试时习惯在代码里临时加print看中间变量。比如成绩统计那题我就打印过排序前的元组列表确认i正确记录了输入顺序。这些临时print在提交前要删掉否则输出会多出内容直接WA。还有一种情况是题目有多个测试用例输入格式是“先读一个T再读T组数据”。这时候很多人忘了循环读T次只处理了一组。看到输出结果只有第一组正确就要立刻检查是不是漏了外层循环。3.3 提交前检查四件事我每次准备点“提交”按钮之前都会按顺序检查四件事第一代码里有没有临时调试用的print。第二输入是否考虑了多行、空行、行尾空格strip()和split()用的位置对不对。第三输出格式是否和题目要求完全一致包括大小写、空格、换行。第四核心变量的命名是否符合逻辑避免把n和m写混。这套检查流程我养成习惯之后一次提交通过的几率提高了不少。很多失败不是算法不行而是这些“小事”没做好。4. 常见问题与排查技巧实录4.1 输入输出格式导致的玄学WA在牛客上做题输入输出格式是最容易出问题的地方。我总结了一下常见的输入场景和对应的处理方式直接整理成表格输入场景处理方法典型坑点只有一组数据每行固定字段逐行input().split()忘记转int第一行是n后面n行数据先用int(input())读n再循环n次读n后忘记处理换行第一行是T后面T组数据外层加for _ in range(T)漏掉外层循环所有数据可能分散在多行用sys.stdin.read().split()一次性读取忘记strip末尾空白我强烈建议在大数据量输入时用sys.stdin.read()而不是input()因为input()在数据量大的时候会有性能开销虽然笔试通常不会因为IO超时但稳妥起见用一次性读取更安全。4.2 边界条件漏判的经典案例边界条件漏判是WA的重灾区。这里分享三个我实际遇到过的案例。第一个案例是字符串为空。当时做一道字符串反转的题我直接s[::-1]输出了没有判断空串。结果那组空串的测试用例直接运行报错因为输入里根本没有这一行。这种问题在本地测试时不容易发现因为你不会主动输入一个空串。第二个案例是取模忘记处理k0。循环右移那题我第一版代码是s[-k:] s[:-k]k0时返回s s[:0]也就是原字符串加上空串结果碰巧正确。但后来题目改成了ASCII码移位k0的情况就不一样了直接导致逻辑错误。所以凡是涉及取模都要单独考虑k0。第三个案例是排序时的并列处理。成绩统计那题如果两个学生总分和语文成绩都相同必须按输入顺序输出。如果直接sorted(students, keylambda x: (-x[0], -x[1]))由于Python的sort是稳定的其实也能保持输入顺序但如果你用了reverseTrue这个稳定性就对不上了。这就是我前面强调要用lambda显式指定排序方向的原因。4.3 时间复杂度估算错误有些同学拿到题不看数据范围直接写暴力解法结果超时。我教大家一个快速估算方法1秒大概能跑10^7到10^8次简单操作。如果n是10^5O(n^2)的算法就是10^10次操作明显超时O(n log n)则很安全。在这套题里成绩统计的排序是O(n log n)括号匹配的栈操作是O(n)都没问题。但如果你遇到需要循环k次的字符串移位k最大10^9逐一移动就会死得很惨。这时候就必须取模把时间复杂度降到O(n)。4.4 几个亲测有效的避坑技巧最后分享几个我自己总结的小技巧。第一所有变量名都用含义清晰的名字。比如用total而不是t用students而不是lst。调试的时候清晰命名能省一半时间。第二写代码时先写处理边界条件的代码再写主逻辑。比如判断空字符串放在最前面判断k0放在前面。这样主逻辑简洁也避免忘记处理边界。第三构造测试数据时专门覆盖“最小值”“最大值”“空值”。比如矩阵翻转时测1行1列的矩阵成绩统计时测n1的情况。这些极值情况最容易暴露问题。第四多看题目给的样例但别只依赖样例。样例通常很温和测不出来边界问题。自己构造一组极端数据跑一遍比自己盯着代码空想要有效得多。这套2020牛客三模的编程题我现在偶尔还会翻出来重新做一遍特别是每次在线笔试前用来热热身、找找手感。我自己的体会是刷题数量固然重要但把一套题吃透比囫囵吞枣刷十套更有用。你如果能把这几道题的边界条件、时间复杂度和编码细节都弄清楚下次面对类似题目的时候一眼就能看穿考点写代码的速度和准确率都会明显提升。