企业官网建设流程全解析

说到机试刷题，我最近一直在坚持更新自己小群里的“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']是 0，0 不小于left（2），说明这个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(key=lambda 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(n+q)。

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] = 0，prefix[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，我准备集中整理模拟类题目的变形，螺旋矩阵这类考边界的题，真的值得再多练几遍。