机试刷题Day4：五大高频算法题解析与边界陷阱

说到机试刷题我最近一直在坚持更新自己小群里的“DHU刷题计划”Day4 的这5道题是我特意按机试真题节奏排的10分钟读题25分钟编码5分钟查边界。网上现在搜机试题跳出来的基本就是几家大厂的笔试合集考来考去也就字符串处理、数组操作、模拟、前缀和这几类。今天这套题正好覆盖了这些高频方向难度卡在“不是一眼就会但静下心能写出来”的区间拿来练机试手感非常合适。我先把题单列出来一道字符串压缩、一道滑动窗口、一道区间合并、一道螺旋矩阵、一道前缀和。这几个考点在真实机试里出现频率很高而且每道题都有明显的“陷阱位”不是单纯背模板就能过的。下面我按做题顺序逐步拆解每道题都会把思路、代码、复杂度和踩坑点说清楚。1. Day4 刷题前的整体思路1.1 机试题和平时刷 LeetCode 的差别很多人平时在 LeetCode 上刷题很顺一到机试就翻车问题几乎都出在“环境差异”上。LeetCode 帮你把输入输出封装好了你只需要实现一个函数机试不一样你要自己处理标准输入、自己组织输出格式而且判题系统对格式非常敏感多一个空格、少一个换行都可能被判错。我 Day4 特意用“完整代码”而不是“核心函数”的方式来写每一道题就是为了模拟机试的真实状态。你可以把 main 函数单独拿出来配一组样例输入直接跑这种训练方式比单纯在编辑器里补函数体要有效得多。另外机试的时间限制通常比较紧Python 选手要特别注意代码常数能用 sys.stdin.readline 就尽量不要用 input()。1.2 为什么选这 5 道题我选题目有个原则不追求偏难怪而是把最高频的“基础算法 细节陷阱”组合着练。字符串压缩考的是相邻字符计数和“读题是否仔细”最长无重复子串考滑动窗口的窗口收缩逻辑区间合并考排序加贪心螺旋矩阵考边界模拟的严谨性前缀和考多组查询下的复杂度优化。这5道题从易到难正好形成一个递进。前面两道字符串题如果你能在 15 分钟内写完且一次通过说明基础还算扎实后面两道数组模拟题才是真正拉开差距的地方因为它们的代码量不大但每一行都藏着小坑。前缀和则是我故意放在最后的“送分题”但送分题反而最容易超时原因下面细说。2. 第一道题字符串压缩读题陷阱2.1 题干与输入输出约定题干是这样输入一行由小写字母组成的字符串长度不超过 10^5要求把连续相同的字符压缩成“字符 出现次数”的形式。比如aaaabbbcc压缩后是a4b3c2。但关键在后面这句如果压缩后的字符串长度没有变短则输出原字符串。很多人在这一步栽了。题目都说了“压缩”大家理所当然认为一定要返回压缩结果结果样例里一旦出现abc这种压缩后反而变长的字符串就直接输出错误结果。这类题在机试里特别多它的核心考点不是算法而是“你有没有把题目读完”。2.2 计数的核心逻辑压缩的逻辑其实很简单用一个计数器从头扫到尾遇到相同字符就让计数器加一遇到不同字符就把上一个字符和它的计数拼到结果里然后重置计数器。这里有个细节计数器要从 1 开始计数因为在遍历到当前字符时你已经默认它出现了一次。循环结束后最后一组连续字符还没有被写入结果所以要单独再补一次。我用的是“与前一个字符比较”的方式也就是s[i] s[i-1]这种方式比双指针定位区间更直观代码量也更少。如果你习惯双指针也可以维护一个start指针指向当前连续段的起点遇到不同字符时把s[start: i]这一段处理好再移动start。2.3 完整代码与复杂度分析import sys def main(): s sys.stdin.readline().rstrip(\n) if not s: print() return res [] cnt 1 for i in range(1, len(s)): if s[i] s[i - 1]: cnt 1 else: res.append(s[i - 1] str(cnt)) cnt 1 res.append(s[-1] str(cnt)) compressed .join(res) print(compressed if len(compressed) len(s) else s) if __name__ __main__: main()这里我特意用了rstrip(\n)而不是strip()因为如果字符串测试用例里首尾有空格strip()会把空格也删掉导致输入失真。当然题目说了只含小写字母一般情况下两者效果一样但养成用rstrip(\n)的习惯能在别的题目里救你一命。时间复杂度是 O(n)只需要一次遍历空间复杂度 O(n)主要花在存储结果字符串上。对于长度 10^5 的输入这个写法完全没有压力。要注意的是res一定要用列表来收集片段不要用res s[i-1] str(cnt)这种字符串拼接。虽然 Python 对字符串拼接有优化但在循环里反复拼接短字符串遇到大数据量时会产生大量临时对象常数会明显变差。2.4 这类题的常见变体字符串压缩在机试里还有很多变体。比如有的题目要求连续字符超过某个阈值才压缩有的要求同时输出解码后的验证信息还有的要求处理数字位数带来的二次歧义比如a12b3这种如果不加分隔符解码时会把12当成两个字符还是十二次重复就说不清了。遇到这种变体核心思路不变只是在拼接时要考虑定长编码或加分隔符。Day4 这道题不需要处理这些但你要知道这种扩展方向因为它非常容易出现在二面加试题里。3. 第二道题最长无重复子串滑动窗口3.1 为什么暴力会挂题目是输入一个字符串输出其中不含重复字符的最长子串长度。比如abcabcbb的最长无重复子串是abc长度 3。暴力的想法很简单枚举所有子串检查每个子串有没有重复字符复杂度 O(n^3) 或者优化到 O(n^2)。但题目字符串长度通常能给到 10^5 级别平方复杂度必挂。这道题的标准解法是滑动窗口复杂度 O(n)。滑动窗口的思路可以这样理解右指针不断向右扩展窗口把新字符纳入窗口当发现窗口内有重复字符时左指针向右移动直到重复字符被排除出窗口。整个过程窗口始终满足“无重复字符”这个条件我们只需要在每次右指针移动后记录窗口的最大长度即可。3.2 窗口收缩的核心细节实现时我会用一个字典used记录每个字符最近一次出现的下标。每次右指针移动到right字符为ch先检查ch是否出现过并且上次出现的下标是否还在当前窗口内也就是判断used[ch] left。如果条件成立说明窗口内有重复字符把left更新为used[ch] 1相当于把重复字符及其左边的部分全部丢弃。这里最容易被忽略的是used[ch] left这个条件很多人直接写if ch in used: left used[ch] 1这在大多数测试用例下能过但遇到abba这种例子就会出问题。流程是这样的遍历到第二个b时left变成 2窗口变成b遍历到第二个a时used[a]是 00 不小于left2说明这个a已经被移出窗口了不能用它来收缩窗口。如果把left错误地更新成 1窗口会倒退答案就错了。3.3 完整代码与变体import sys def main(): s sys.stdin.readline().rstrip(\n) used {} left 0 max_len 0 for right, ch in enumerate(s): prev used.get(ch, -1) if prev left: left prev 1 used[ch] right max_len max(max_len, right - left 1) print(max_len) if __name__ __main__: main()代码很短但每一行都值得反复推敲。used.get(ch, -1)这句把默认值设成 -1是为了让第一次出现的字符不触发prev left的判断因为任何合法的left都大于等于 0。你可以设成任何负数效果一样。这类题的变体很多最常见的是“最多包含 K 个不同字符的最长子串”和“包含所有字符的最短子串”。核心都是滑动窗口只是收缩条件不同。如果你能把这道题吃透那些变体基本只需要改一下条件判断就能解。4. 数组与模拟区间合并与螺旋矩阵4.1 区间合并排序贪心的取舍这道题输入若干行每行两个整数表示一个区间的左右端点要求合并所有重叠区间。比如[1,3]和[2,6]重叠合并成[1,6]。思路是先按左端点排序然后依次扫描。排序之后如果当前区间的左端点小于等于“当前合并区间”的右端点说明它们有交集可以合并否则说明当前区间和前面的合并区间彻底断开了直接把前面的合并区间保存下来开始一个新的合并区间。这里有一个关键细节合并时右端点要取两个区间右端点的最大值因为排序只保证了左端点有序并没有保证右端点也有序。比如[1,6]和[2,5]当前合并区间的右端点是 6新来的区间右端点是 5如果直接拿新区间的右端点覆盖合并结果就错了。务必用max处理。import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) intervals [] idx 1 for _ in range(n): intervals.append([int(data[idx]), int(data[idx 1])]) idx 2 intervals.sort(keylambda x: x[0]) merged [intervals[0]] for start, end in intervals[1:]: if start merged[-1][1]: merged[-1][1] max(merged[-1][1], end) else: merged.append([start, end]) out [] for start, end in merged: out.append(f{start} {end}) print(\n.join(out)) if __name__ __main__: main()需要注意相邻区间的情况比如[1,2]和[2,3]按常规定义左右端点闭区间且重叠条件是start merged[-1][1]所以这两个区间会合并成[1,3]。如果题目要求的是“严格不重叠才合并”就要改成start merged[-1][1]。这类细节必须在读题时确认清楚。这个题的时间复杂度 O(nlogn)瓶颈在排序空间复杂度 O(n)。变体“会议室安排”其实就是一个判断区间是否冲突的题按结束时间排序后贪心选择即可和区间合并是一对孪生题。4.2 螺旋矩阵边界模拟防越界这道题输入一个矩阵要求按顺时针螺旋顺序输出所有元素。比如 3 行 3 列的矩阵从左上角开始转圈输出。解法是维护四个边界上边界top、下边界bottom、左边界left、右边界right。每次按“从左到右、从上到下、从右到左、从下到上”的顺序走一圈每走完一个方向就收缩对应的边界。import sys def main(): data sys.stdin.read().strip().split() if not data: return m int(data[0]) n int(data[1]) matrix [] idx 2 for _ in range(m): matrix.append([int(x) for x in data[idx:idx n]]) idx n top, bottom 0, m - 1 left, right 0, n - 1 res [] while left right and top bottom: for j in range(left, right 1): res.append(matrix[top][j]) top 1 for i in range(top, bottom 1): res.append(matrix[i][right]) right - 1 if top bottom: for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 if left right: for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 print( .join(map(str, res))) if __name__ __main__: main()这段代码里最容易被忽略的就是后面两个方向的if判断。比如矩阵只有 1 行时走完“从左到右”后top已经大于bottom如果还继续走“从下到上”的循环就会越界。加上if top bottom和if left right之后每一层循环都保证访问的边界仍然合法。这道题需要手推一个小用例来验证边界。我通常会拿 1 行 3 列[1,2,3]和 3 行 1 列[[1],[2],[3]]这两个极端形状来测能一次通过基本就稳了。螺旋矩阵在真实机试里出现的频率不低因为它代码量不大却能非常有效地考察你对手写边界控制的敏感度。5. 查询优化前缀和的典型应用5.1 为什么直接求和会超时最后一道题是经典的前缀和场景第一行输入数组长度 n 和查询次数 q第二行输入 n 个整数接下来 q 行每行两个整数 l、r要求输出闭区间[l, r]的和。最直接的做法是每次查询都循环累加单次查询 O(n)总复杂度 O(nq)。如果 n 和 q 都是 10^5 级别总运算量会达到 10^10在机试里必挂。前缀和的核心思想是把“区间和”转换成“两个前缀和的差”。我们预处理出一个prefix数组prefix[i]表示原数组前 i 个元素的和那么区间[l, r]的和就等于prefix[r] - prefix[l-1]。预处理 O(n)每次查询 O(1)总复杂度降到 O(nq)。5.2 完整代码与下标对齐的细节import sys def main(): input_data sys.stdin.read().strip().split() if not input_data: return idx 0 n int(input_data[idx]) q int(input_data[idx 1]) idx 2 arr [int(x) for x in input_data[idx:idx n]] idx n prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] arr[i] res [] for _ in range(q): l int(input_data[idx]) r int(input_data[idx 1]) idx 2 res.append(str(prefix[r] - prefix[l - 1])) print(\n.join(res)) if __name__ __main__: main()这里要注意下标问题。题目给的下标通常是 1-based也就是第一个元素的编号是 1。我构建prefix时特意让prefix[0] 0prefix[1]对应arr[0]这样一来直接用题目给的l、r计算就不用做减一转换。如果题目是 0-based 下标记得把l和r都加 1 再查前缀和否则结果会错一位。另外这个输入格式用sys.stdin.read().split()一次性读取是最稳的因为 q 可能很大逐行input()的调用开销会拖慢程序。把读取到的所有数据放到一个列表里再用一个指针逐个取数这种“滚动读取”的模式在机试多行输入里非常实用。这类题扩展方向很明确二维前缀和用来快速求子矩阵和差分数组用来处理多次区间增量再统一求最终值。如果你今天的题单有余力我建议把这两个扩展也过一遍因为它们和区间合并一样都属于“高频题型中的高频题型”。6. 机试题通排心得输入输出、超时与边界6.1 输入输出踩坑记录这几道题做下来我发现自己和身边朋友踩得最深的坑都在输入输出上。比如strip()和rstrip(\n)的差别前面已经说过再比如输出一长串数字时用循环print(x)每次打印一行不如把所有结果收集到列表里最后用\n.join()一次性输出因为后者只调用一次写操作。还有一个容易被忽略的点sys.stdin.read()会一次性读入所有内容包括末尾换行所以strip()之后如果输入为空data会是空列表这时一定要记得加if not data: return的判空保护。很多人在输入为空时不处理直接访问data[0]就会抛IndexError在机试里这样的错误会直接算零分。6.2 超时怎么快速定位如果提交后显示超时我的排查顺序是先看复杂度再看常数最后看死循环。复杂度的问题是硬伤比如本来应该用前缀和却写成了每查询一次求和一次这种只能重写算法。常数层面的问题集中在输入输出方式比如大循环里用input()和print()。死循环排查重点看 while 循环和双指针更新的位置。拿螺旋矩阵举例如果你走完一个方向忘了收缩边界或者收缩顺序写错就会在while left right and top bottom里无限循环。我遇到这类问题时习惯在关键位置加临时打印输出当前的left/right/top/bottom和指针位置跑一个小样例就能定位是哪个方向更新错了定位后记得把打印删掉再提交。6.3 边界条件自查清单我每次写完代码会先拿几个固定的极端用例过一遍基本能挡掉 80% 的错误。这里分享一个我自己常用的清单空输入字符串为空、数组为空、矩阵为空能不能直接给出合法输出而不报错。单元素长度为 1 的字符串、只有一个元素的数组、1 行 1 列的矩阵。全相同所有字符相同、所有数组元素相同、区间全部嵌套。完全相反每个字符都不同、区间互不重叠且有间隔。最大规模拿 n 或 m 接近上限的数据测运行时间。这个清单每道题都跑一遍能发现大量平时注意不到的边界问题。比如字符串压缩里s只有一个字符时循环根本不执行全靠循环外的res.append(s[-1] str(cnt))兜底螺旋矩阵里 1 行多列和多行 1 列都靠两个if判断兜底。这些不是玄学而是每一个坑都能在这个清单里对应到一个具体用例。我自己做这套题最深的感受是机试题的难点不在于算法本身而在于你愿不愿意在写代码之前多花两分钟去确认输入输出格式、边界定义和复杂度约束。今天这 5 道题每道题的算法思想都称不上难但每一道都能筛掉一批“粗心的人”。如果你也在刷机试建议把今天这套题打乱顺序不看答案自己模拟一次完整的机试流程你会发现收获比看十篇总结都大。下一期的 Day5我准备集中整理模拟类题目的变形螺旋矩阵这类考边界的题真的值得再多练几遍。