★ FEATURED ARTICLE 1. 同一道题两种写法ACM模式和核心代码模式的分野到底在哪我印象很深的一次经历是帮一个朋友看他的笔试代码。那道算法题本身不难就是经典的区间合并他在核心代码模式的平台上一遍过逻辑干净利落。结果同样一道题换到需要自己处理输入输出的笔试环境里他交了七次全是答案错误。最后排查出来的原因是他读一组数据读一行但题目给的数据是同一行的两个数被一个多余空格隔开split()之后的长度判断写死了。这事说明一个事实算法题的能力其实分两层一层是算法设计本身另一层是把算法接到真实数据流上的工程能力。ACM模式和核心代码模式恰好分别放大了这两层中的一层。所谓核心代码模式就是你在平台上只写一个函数或者一个类的方法比如def twoSum(self, nums, target)这种输入被平台打包成现成的参数对象输出也被平台自动比对你只管中间的算法逻辑。而ACM模式是国际大学生程序设计竞赛沿用下来的那一套程序从标准输入读数据从标准输出写结果判题系统拿你的输出和标准答案逐字节比对。整条数据链路从头到尾都由你自己负责。这两者不是难和易的关系而是责任边界完全不同。核心代码模式下平台帮你承担了读数据、解析、类型转换、结果输出、格式校验的全部工作ACM模式下这些活儿全落在你身上算法本身反而可能只占整个代码的三分之一。我后来把这件事想明白了很多人抱怨我算法会啊怎么笔试就是过不了根源就在于他把ACM模式当成了核心代码模式来写以为写完核心逻辑就完事了。实际上读入和输出才是ACM模式里最高频的失分点。1.1 核心代码模式被精心裁剪过的半个工程核心代码模式的本质是把一道完整题目里和算法无关的部分全部剥掉只留一个函数签名给你。以常见的两数之和为例你在平台上看到的界面是class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: # 你只需要写这里 pass这个函数签名里已经隐含了大量约定nums一定是一个合法的整数列表target一定是一个整数返回值一定是一个长度固定为2的列表而且答案保证存在。你不需要考虑输入是不是有多组测试、不需要考虑列表为空怎么办、不需要考虑数字超不超出范围。这种模式的好处是反馈快、心智负担低特别适合刚开始练算法思路的阶段。你可以把全部注意力放在用什么数据结构、时间复杂度能不能过上而不被读入输出干扰。但它的代价也很明显它训练出来的是算法思维不是完整的工程实现能力。你写出来的代码是一个半成品缺了前半段的输入解析和后半段的输出格式化。很多公司在笔试环节特意用ACM模式看的就是你有没有把半成品补成完整程序的能力。1.2 ACM模式算法只是其中一环ACM模式的典型形态是这样判题系统给你一段输入文本你的程序要自己把它读进来处理完之后把结果打印出去。举个例子题目说第一行一个整数 T表示测试数据组数接下来 T 行每行两个整数 a 和 b输出 ab那么完整的程序长这样import sys def main(): data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 out [] for _ in range(t): a int(data[idx]); idx 1 b int(data[idx]); idx 1 out.append(str(a b)) sys.stdout.write(\n.join(out)) main()可以看到真正算a b的那一行只有一处其余全是IO。这就是ACM模式的真实面貌你写的是一个可以独立运行的程序不是一个函数。我个人的体会是ACM模式对细节控制力的要求远高于核心代码模式。空格多一个少一个、换行有没有、每组数据之间要不要空行、浮点数保留几位小数、大小写是否一致任何一处对不上就是答案错误而且平台不会告诉你错在哪一位只会告诉你通过率 0%。1.3 两种模式的差异对照把这两者放在一起对比差异会非常直观维度核心代码模式ACM模式入口平台给定的函数/方法自己写的main输入来源平台注入的参数标准输入输出目标函数返回值标准输出多组数据平台循环调用自己写循环格式校验平台负责自己负责主要失分点算法错误、边界漏判读入错误、输出格式错误调试方式平台报错信息自己打印或本地跑看完这张表你应该能理解为什么很多人算法会但笔试挂。两种模式考察的能力确实不完全重叠。核心代码模式重算法ACM模式重全链路。接下来我就按照一个真实的排查顺序从输入读到输出写把ACM模式里那些坑一个个拆开讲。2. 输入读取这关从 input() 到 sys.stdin 的写法与性能差异ACM模式里输入读取是第一道关卡也是最容易让人在细节上翻车的地方。我见过太多人算法思路完全正确结果卡在怎么把这一坨数据读进内存上。这一章我按 Python 的视角来展开因为用 Python 打笔试的同学最多同时也会顺手说下其他语言的处理方式。2.1 逐行读还是整体读两种流派适用场景不同Python 读标准输入有几种常见写法我先说最直观的一种逐行读n int(input()) for _ in range(n): a, b map(int, input().split()) print(a b)这段代码看起来很干净逻辑也清楚。input()每次读一行并去掉末尾换行符split()按空白切分map(int, ...)批量转成整数。对于行数不多的题目这种写法完全够用。但这里有个性能上的问题需要提醒input()在底层会去操作标准流每次调用都有额外的开销。当数据规模到十万行、百万行级别逐行读会明显变慢有些题目会因为这个超时。我踩过一次这样的坑一道题本地测的时候数据是几千行跑得飞快结果提交之后超时换成整体读就过了。整体读的写法是import sys data sys.stdin.read().split() # 一次性把整个输入按空白切分sys.stdin.read()会把标准输入从头读到尾读成一个大字符串split()不带参数时会按任意空白字符空格、换行、制表符切分所以不管你原来的换行和空格怎么分布结果都是一个扁平的字符串列表。之后你只需要用一个下标指针在列表里来回移动就能取出所有数据。这种写法只做一次IO剩下的都是内存操作性能上明显更好。提示用整体读的时候记得用一个变量比如idx记录当前读到哪了每取一个就自增。这个模式在多组数据、矩阵输入的场景下尤其顺手因为不用去操心行和行之间的对应关系。那什么时候用逐行读更合适呢我的经验是当输入包含字符串行、需要保留行结构的时候。比如题目给你一段文本每一行是一个单词可能带空格这时按行读把整行保留下来比先打散再拼回去要稳得多。sys.stdin.read().split()会把空格也切掉如果某行数据本身靠空格分隔但又不能切比如字符串里含空格那就得换思路。import sys for line in sys.stdin: line line.strip() if not line: continue # 需要整行处理的逻辑for line in sys.stdin这种方式在 Python 里是推荐的行迭代写法比反复调input()也要快一些。2.2 多组测试数据的三种终止条件ACM模式里最让人头大的不是读一行而是不知道什么时候停。多组测试数据的结束条件常见的有这么几种识别错了就直接死循环或者少读数据。第一种第一行给组数。这是最规范的一种题目会明确说第一行一个整数 T。你只需要读一个 T然后循环 T 次。这种情况下不会读多也不会读少最省心。第二种读到文件结尾为止。题目会说输入包含多组测试数据处理到文件结束或者多组数据每组一行。这时候 Python 里常用的处理是import sys for line in sys.stdin: line line.strip() if not line: continue a, b map(int, line.split()) print(a b)这里我特意加了一个if not line: continue的判断因为有些输入文件的末尾会有一个空行如果不跳过split()出来的列表是空的map解包会直接报值不够的错误。这个空行的坑挺隐蔽的本地自己造测试数据的时候往往不会加到了真实数据上就崩了。第三种用一个特殊值作为结束标志。题目会说输入以 0 0 结束或者当 n 为 0 时输入结束。这种要小心结束标志本身不应该被处理成正常数据。import sys for line in sys.stdin: line line.strip() if not line: continue a, b map(int, line.split()) if a 0 and b 0: break print(a b)判断顺序很关键先判断是不是结束标志再进入正常处理逻辑。如果写反了会把 0 0 也算成一组输出多出一行。还有一种相对少见但确实存在的情况输出以某个特殊格式标识最后一组或者每组数据后面要不要空行由题目规定。这类情况我在第 3 章会展开讲。2.3 输入解析里那些阴阳怪气的格式除了终止条件输入本身的结构也有很多花样。我整理了几种在笔试和期末机考里出现频率比较高的矩阵输入。题目说接下来一个 N 行 M 列的矩阵每行 M 个整数。用整体读的写法最舒服先读 N 和 M然后连续取 N×M 个数字按行组装。如果矩阵里的数字没有负数直接用列表推导也能读。一行的第一个数是这行元素的个数。这种格式需要先读个数再按个数取后面的值。用整体读加下标指针天然适配这种结构。数据之间用逗号或分号分隔。这种不能直接split()得先按分隔符切开再处理。比如1,2,3这种可以line.split(,)之后再转整数。字符串里含空格。只能按行读把整行保留不能先打散。混合类型一行里既有数字也有字符串。这种情况用整体读要小心因为split()出来的都是字符串转数字之前得判断清楚哪几个该转。关于矩阵输入我特别想说一个心得用整体读加下标指针的写法可以让矩阵输入和普通输入共用同一套骨架。你不用去关心某个数字具体在第几行第几列只要按题目给的顺序依次取出来就行。这种写法让我在处理复杂输入结构的时候省了很多脑细胞。import sys def main(): data sys.stdin.read().split() idx 0 n int(data[idx]); idx 1 mat [] for i in range(n): row [] for j in range(n): row.append(int(data[idx])); idx 1 mat.append(row) # 后续算法 main()2.4 其他语言读输入的对应写法用 C 的同学常见的选择是cin和scanf。cin写起来方便scanf在极端数据量下更快。很多时候为了保险会在main开头加一句ios::sync_with_stdio(false); cin.tie(nullptr);关闭同步之后cin的速度能和scanf差不多。Java 的话Scanner简单但慢数据量大的时候用BufferedReader加StringTokenizer更稳。这些细节在算法竞赛圈已经是常识但刚到笔试环境的同学往往不知道。3. 输出格式的细节多一个空格就是答案错误如果说输入读取是ACM模式的第一道坎那输出格式化就是第二道而且它比输入更无情感因为大部分判题系统做的是逐字符比对多一个空格就是错。这一章我把输出环节里最容易出问题的几个点拎出来。3.1 末尾空格和换行最经典的失分点先说一个非常基础但翻车率极高的问题每行输出的末尾多了一个空格。这种错误通常发生在循环里拼接字符串的时候# 有问题的写法 for i in range(len(nums)): print(nums[i], end )这样写会在最后一个元素后面也留一个空格。如果判题系统严格按字符比对直接判错。正确的做法有两种一种是拼成一个列表最后统一用joinprint( .join(map(str, nums)))另一种是先判断是不是最后一个元素out [] for i, x in enumerate(nums): if i 0: out.append( ) out.append(str(x))我更推荐第一种join写法干净而且不会漏掉任何边界。换行的问题同理最后一行之后要不要再来一个换行。绝大多数系统不在乎末尾多一个换行但也有少数系统会严格比对。我的做法是统一用\n.join(结果列表)然后一次性write出去末尾不加换行。这个写法在绝大多数平台上都稳。3.2 每组数据之间要不要空行多组数据的题目里有时候会要求每组输出之间空一行。注意是之间不是每组之后。这两个描述差别很大每组输出之后空一行所有组后面都空包括最后一组。每组输出之间空一行只有相邻两组之间有空行第一组前面和最后一组后面都没有。我见过有人按照之后的理解去写结果最后一组多了一个空行被判定为格式错误。稳妥的写法是维护一个计数器第一组不输出空行之后每组先输出一个空行再输出内容import sys def main(): data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 out_lines [] for case in range(t): if case 0: out_lines.append() a int(data[idx]); idx 1 b int(data[idx]); idx 1 out_lines.append(str(a b)) sys.stdout.write(\n.join(out_lines)) main()注意out_lines.append()这种做法会把空字符串也作为一行拼进去join之后就自然产生了空行比手动加\n\n要清晰。3.3 Case 编号、大小写和浮点数精度有几类输出格式是笔试里的常客我逐条说一下。Case 编号。题目经常要求输出成Case #1: 12这种格式。这里要注意三点编号从 1 开始、#和编号之间不能有空格、冒号后面有一个空格。这种格式我建议直接用字符串格式化写print(fCase #{case 1}: {result})大小写。有些题目要求输出YES或NO有些是Yes或No还有些是Possible和Impossible。这种只能仔细看题面写之前把题目给的示例复制出来对齐一遍。我吃过一次亏题目里写的是Yes我顺手写成了YES结果三组测试全错。浮点数精度。题目说保留两位小数那就得用{:.2f}.format(x)或者 f-string 的f{x:.2f}。这里有一个很容易被忽略的点四舍五入的方向。Python 的格式化默认用的是银行家舍入round half to even也就是说2.675格式化到两位可能会变成2.67而不是2.68因为二进制浮点数本身存不准。如果题目对精度要求严格通常出题人会设置误差容限但期末机考里偶尔会要求精确到某一位这种时候如果答案对不上可以先怀疑是不是浮点数精度的问题。大数输出。Python 自带大整数一般不用操心。但如果题目要求对结果取模记得在每一步运算之后都取模不要等到最后才取否则中间结果可能膨胀得非常大拖慢速度。4. 核心代码模式的暗规则函数签名背后的那些约束说完了ACM模式再回到核心代码模式。很多人觉得这种模式简单因为平台把IO都包了。但实际上核心代码模式也有一套自己的规则违反了照样过不了。这一章专门讲这些不那么明显的地方。4.1 函数签名和类型标注是最硬的约束核心代码模式里平台通常已经给了一个类和方法签名比如class Solution: def lengthOfLongestSubstring(self, s: str) - int: pass这个签名是不能改的。函数名、参数个数、参数名、返回类型全都得保持一致。有人图方便把s改成string觉得可读性更好结果平台找不到对应的方法直接报错。也有人把返回值类型改掉比如本来该返回整数他却返回了一个列表编译能过但比对失败。还有一类是参数里带上了平台自定义的数据结构最常见的是链表和二叉树# 平台可能给定的 ListNode 定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: pass这种题目里你操作的是平台构造好的链表节点对象不是数组。返回值也得是一个节点对象不能返回一个列表。我见过有人习惯性地把链表转成数组再处理最后返回数组结果平台比对的类型不匹配。4.2 原地修改还是返回新对象有一类题目会明确要求原地修改或者空间复杂度 O(1)。这其实是在约束你的实现方式。比如移除数组中的重复元素题目可能要求把不重复的元素放到数组前面并返回新的长度不允许额外开一个数组。这种约束的意义在于它考察的不是你能不能做出来而是你能不能在限制条件下做出来。核心代码模式的题目里不允许额外空间是很常见的附加条件。写之前一定要读清楚这一段否则算法再对也过不了。判断方法是如果方法签名里有nums这样的参数并且题目说原地修改那就直接对nums做替换操作函数内不新建长度等于len(nums)的额外列表。4.3 全局变量在多次调用之间的残留问题这是一个相对隐蔽的坑。有些核心代码模式的平台会用同一份代码跑多组测试用例同一个 Solution 实例或者同一个类的多个实例会被反复调用。如果你在类里定义了类变量或者用了模块级的全局变量来累积状态就可能在下一组测试里被上一次的残留数据污染。# 有隐患的写法 class Solution: cache {} # 类变量多次调用之间会保留 def solve(self, n): # 依赖 cache 的逻辑 ...稳妥的做法是每个方法内部的临时状态都定义在方法里不要挂在类或者模块上。如果确实要用缓存优化也要想清楚这个缓存能不能跨测试用例复用。对于大多数笔试场景直接写在方法内部最省心。5. 从核心代码模式改写为ACM模式的完整流程讲完了两边的规则接下来讲一个非常实用的技能怎么把一道核心代码模式的题目改造成ACM模式的完整程序。这个技能在期末机考、企业笔试里几乎一定会用到因为出题人给的示例通常是核心代码风格的函数但真正提交时你面对的是命令行程序。5.1 第一步先写出IO外壳别急着写算法我的习惯是反过来的拿到题目之后先不碰算法先把输入输出外壳搭好让它能原样读进来、原样打出去。这样一来哪怕算法还没写你至少能确认输入读对了。具体做法是看题目给的输入格式判断是第一行给组数还是读到EOF还是以特殊值结束。用整体读加下标指针的方式把数据读到一个合适的数据结构里。先print一下读到的数据或者直接输出一个占位结果验证读入没有少读、没有多读。确认无误之后再把算法逻辑填进去。这个顺序能帮你把问题域缩小。如果最后答案错了你能很快判断是读入错了还是算法错了。5.2 第二步把核心函数原样搬进来假设你手里已经有一个核心代码模式的函数def merge_intervals(intervals): intervals.sort(keylambda x: x[0]) result [] for start, end in intervals: if not result or start result[-1][1]: result.append([start, end]) else: result[-1][1] max(result[-1][1], end) return result把它搬进ACM程序的骨架里时你只需要把输入解析出来的数据构造成对应的参数类型调用函数再把返回值按题目要求的格式打印出去import sys def merge_intervals(intervals): intervals.sort(keylambda x: x[0]) result [] for start, end in intervals: if not result or start result[-1][1]: result.append([start, end]) else: result[-1][1] max(result[-1][1], end) return result def main(): data sys.stdin.read().split() idx 0 n int(data[idx]); idx 1 intervals [] for _ in range(n): a int(data[idx]); idx 1 b int(data[idx]); idx 1 intervals.append([a, b]) res merge_intervals(intervals) out [] for start, end in res: out.append(f{start} {end}) sys.stdout.write(\n.join(out)) main()你可以看到核心函数一行没改只是外面套了一个读入和输出的壳。这就是我推荐的工作方式核心逻辑和IO逻辑分离两边各写各的互不干扰。5.3 链表和二叉树这类结构怎么在ACM模式里搭前面用的是数组那如果题目涉及链表或者二叉树怎么办核心代码模式里平台会帮你构造好这些对象ACM模式里你得自己从输入数据里把它们搭出来。以单链表为例题目通常给一行数字表示链表的各节点值。你需要自己从数组构造链表class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_list(vals): dummy ListNode() cur dummy for v in vals: cur.next ListNode(v) cur cur.next return dummy.next二叉树稍微复杂一点题目可能给的是层序数组也可能给的是前序加中序。层序数组构造的方式类似 BFS用一个队列维护待处理的父节点。这里我不展开完整的构造代码但思路是一样的先把输入数据解析成数组再用数组构造出目标数据结构最后交给核心函数。提示如果题目里出现了链表或二叉树输入格式通常在题面里会写清楚。比如第一行一个整数 n 表示节点个数第二行 n 个整数表示节点值这种就是数组构造如果只给一个前序序列和中序序列那就要按遍历规则重建。读题的时候把这一段抓准比什么都重要。5.4 多组数据下的状态重置ACM模式里如果有多组数据还有一个隐藏问题每一组数据之间你的程序状态要是干净的。如果核心函数里用了类变量或者模块级的全局变量来缓存第二组数据就可能被污染。我一般会把整个处理逻辑包在一个函数或者一次循环体里确保每个用例都从空状态开始def main(): data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 out [] for _ in range(t): n int(data[idx]); idx 1 nums data[idx:idx n] idx n # 每个用例都重新构造数据、重新计算 result solve([int(x) for x in nums]) out.append(str(result)) sys.stdout.write(\n.join(out))把solve写成纯函数、不依赖外部可变状态是最省心的做法。6. 期末编程题和在线笔试里的临场取舍算法设计与分析的期末编程题、企业的在线笔试场景和纯刷题不太一样。刷题的时候你可以慢慢想、反复试但在考场上时间是硬约束而且往往同时有好几道题。这一章讲一些临场的处理方式都是我自己在考场上摸出来的。6.1 先过样例再想优化拿到题的第一件事不是想最优解而是先用最笨的办法把样例跑通。哪怕是最朴素的暴力枚举只要能把题目给的示例输入跑出示例输出你就保证了一件事读入和输出格式是对的。这一点特别重要。很多人一上来就想完美解法结果想了半小时写出来的代码样例都跑不过最后时间去了一大半连分数都拿不到。正确的节奏是先用暴力把框架搭起来提交一次确认格式没错再在这个基础上优化。暴力实现的耗时通常在几分钟以内但它换来的是格式正确这个确定性。有了这个保底后面优化就是纯收益。6.2 本地自测把样例存成文件在线笔试系统一般会给你几组样例输入输出。我的做法是在本地把这些样例存成文本文件然后用命令行重定向测试python solution.py input.txt这样你就能在本地看到自己的输出和样例输出做逐字符比对。比在网页上反复刷新提交要快得多而且能看到完整的输出内容方便比对空格和换行。如果手头没有样例文件那就自己造几组。造的时候特别留意边界情况数据最小是多少、最大是多少、有没有负数、有没有重复元素。这些边界是判题系统最爱用的额外测试点。6.3 打印调试要记得删调试的时候用print打印中间变量很方便但提交前一定要把这些调试输出删掉。我见过有人调试打印忘了删输出里多了一行中间结果被判定为格式错误。稳妥的做法是用sys.stderr.write打印调试信息因为标准错误不会混进标准输出判题系统不会去比对这一路内容。import sys sys.stderr.write(fdebug: idx{idx}\n)这样调试信息你在本地能看到提交之后也不影响正式输出。6.4 时间分配的粗略原则如果是期末机考一般题目数量不多三到五道我建议一道题拿到最初的暴力分之后先去看下一道把所有题都过一遍再回头优化能拿更多分的题。因为很多题目的部分分是按测试用例给的你把每道题的简单用例都过了总分往往比死磕一道难题要高。在线笔试同理。笔试通常给两到三小时题目难度是梯度分布的。先把能拿的分拿到手再去啃硬骨头。6.5 一个关于模式的补充观察刷题刷到一定程度之后你会发现ACM模式写的代码稍微改一下就变成了核心代码模式的解法——把IO壳去掉把主逻辑提取成一个函数就完事了。反过来也一样。所以这两种模式并不是对立的两套技能而是一件事的两端。我在练习的时候习惯同一道题两种模式都写一遍。核心代码模式用来打磨算法本身ACM模式用来检验自己能不能把它接到真实数据流上。两边都过了才算是真正掌握了这道题。这个习惯坚持一段时间之后我笔试的通过率明显上来了。原因很简单我不是在算法上比别人强多少而是我不再会因为一个多余的空格、一个读漏的换行、一个没判断的结束标志而丢分。这些看起来不起眼的细节加在一起就是及格线和优秀线之间的差距。练习题目的过程中我还会刻意去整理一份自己的IO模板文件把读 T 组读到 EOF多组带空行这些常用外壳各存一份。到了考场上读清楚输入格式之后直接挑一个模板改改就用能省下至少十分钟。这十分钟往往就是多看一道题的时间。
阅读完成 · 觉得有帮助？
