如果只能给准备华为机考的人推荐一道必刷题我会毫不犹豫地说DNA 序列。这道题在牛客华为机试的题库里编号是 HJ63听起来像生物信息学的门槛实际上就是一个披着字符串外衣的滑动窗口问题。很多第一次接触华为机考的人在牛客网在线做题时会发现它跟自己习惯的 LeetCode 模式完全不同连输入输出都要自己写而 DNA 序列恰好就是这样一道能帮你把机考手感练出来的题。这篇文章从真题描述讲起依次拆解暴力解法和滑动窗口的推导过程、三种主流语言的实现细节、真实机考环境下的答题策略以及从这题延伸出去的一整类滑动窗口题。无论你是校招新人、准备 OD 笔试还是想快速找回手感的老手都能照着这篇的思路走一遍把这道送分题稳稳拿下。为了阅读方便后面我统一用 L 表示 DNA 序列总长度用 k 表示题目要求的子串长度。1. 真题还原题面长什么样考点躲在哪里1.1 一份接近原题的描述题目描述我给一个接近原题的版本一个 DNA 序列由 A、C、G、T 四种字母组成。现在给定一段 DNA 序列字符串和一个正整数 n需要你找出所有长度为 n 的子串中GC 比例最高的那个子串。所谓 GC 比例是指子串中字符 G 和 C 的出现次数占整个子串长度的比例。如果有多个子串的 GC 比例相同输出最早出现的那一个。输入描述输入分两行第一行是一个字符串 s第二行是一个正整数 n。输出描述输出一个长度为 n 的字符串表示 GC 比例最高的子串。标准示例输入 ACGT 2 输出 CG这个示例很直观ACGT 长度为 2 的子串依次是 AC、CG、GT其中 GC 数量分别是 1、2、1最高的是 CG。但光看示例看不出边界实际评测里可能出现 n 大于字符串长度、字符串里全是 A、多组数据同时输入等情况。1.2 两个容易跑偏的读题方向第一个方向是误以为要算浮点比例。GC 比例 G 的个数 C 的个数/ k既然所有候选子串的长度都是 k分母相同比比例本质上就是比分子。直接数 G 和 C 的数量用整数比较既避免浮点误差又省掉多余的除法开销。我在实际代码里从来不会去算比例只维护一个整数 cnt。第二个方向是想 KMP、后缀数组这类高级字符串算法。这道题不涉及模式匹配、不回文、不公共前缀就是固定长度的区间统计最合适的算法就是滑动窗口没有之一。很多人一看题目名字带DNA就觉得要上生物信息学的黑科技其实命题人只是套了一个科学外衣内核简单得不能再简单。1.3 这道题在华为机考中的位置感华为机考一般是三道题总时长 150 分钟分数结构常见是 100 200 200不同批次和岗位会有差异。DNA 序列通常作为第一题或第二题难度评级简单到中等。它在题库里的意义不只是让候选人拿分更是考察你有没有把业务包装还原成基础算法的能力。DNA 是生物学背景但底层数据结构就是字符串属于区间统计模型工程上这类问题非常常见固定时间窗口内的流量峰值、固定距离内的信号强度、固定周期内的温度均值全是同一套思路。第一题在整场机考里是保底分建议无论如何都要吃下来。如果第一题卡了太久后面的大题基本没有时间做。很多从华为机考回来的人复盘时都会说不是难题做不出是简单题浪费了太多时间。1.4 题目给我们的三个隐藏信息仔细读题能抓到三个关键信息要求子串是连续的而且是固定长度 k这是典型的固定窗口比较目标是 GC 数量因为分母固定等价于 GC 比例多个答案取最早出现的意味着比较时必须用严格大于不能大于等于。很多人刷 LeetCode 刷习惯了会忽略这些隐藏条件。其实这三点只要抓住整体的代码框架就已经出来了一个固定长度的窗口从左往右滑边滑边记录最优值滑完输出最优方案。2. 从暴力数一遍到滑窗挪一遍完整推演2.1 先写暴力确保题意理解没有偏差暴力解法是最容易验证自己有没有读错题的。枚举所有起点 i范围是 [0, L-k]对每个起点截取长度为 k 的子串统计 GC 数量保留最大数量和它对应的子串。s ACGT k 2 max_cnt -1 ans for i in range(len(s) - k 1): sub s[i:i k] cnt sub.count(G) sub.count(C) if cnt max_cnt: max_cnt cnt ans sub print(ans)暴力解法有两个作用。第一在你没有完全想清楚滑动窗口边界时先拿暴力把样例跑通确认自己的输出是对的避免题意理解偏差。第二后面写完滑动窗口后用暴力去对拍随机生成一串 DNA 和随机 k对比两个解法的输出是否一致。对拍能堵住绝大多数边界错误是我刷题时非常依赖的验证手段。2.2 复杂度分析暴力的问题不在常数在量级假设字符串长度为 L窗口大小为 k。暴力枚举的起点数有 L-k1 个每个子串统计要遍历 k 个字符因此总时间复杂度是 O((L-k1) * k)最坏情况下约 O(L * k)。有人会觉得字符串处理几千个字符就算 O(L*k) 也没啥。但机考的评测数据不会只有一个小样例。假设 L 达到 10^4k 取 5000暴力就是 5000 万次基本操作。C 可能还撑得住Python 在这种量级下跑满全部隐藏用例超时的概率非常大。华为机考的 Python 时限一般比 C 宽但不会无限宽。而滑动窗口整体遍历一遍字符串每个字符在进入窗口和离开窗口时各处理一次总的操作是常数倍的 L也就是 O(L)。从 O(L*k) 到 O(L)这个优化不是抠常数是真的降了一个数量级。2.3 滑动窗口的直观理解一扇移动的玻璃窗你可以把长度为 k 的窗口想象成一扇玻璃窗贴在字符串上。窗口在位置 i 时看到的内容是 s[i] 到 s[ik-1]挪一格左边会走出一个字符右边会走进一个字符窗口内的其他字符原封不动。所以维护一个变量 cnt 表示当前窗口里 G 和 C 的总数。窗口右移一格时只需要处理两件事走出窗口的字符 s[i] 如果是 G 或 Ccnt 减 1走进窗口的字符 s[ik] 如果是 G 或 Ccnt 加 1。因为每次移动只处理两个字符单次是 O(1)整体是 O(L)。需要特别注意的是第一个窗口必须先手动初始化。比如 i0 时的窗口是 s[0:k]这个窗口的 cnt 要先用一个循环数出来然后再让窗口开始滑动。很多人就是漏掉了第一步初始化导致 max_cnt 初始值是 0输出永远错误。别笑这一步真的非常容易丢。2.4 辅助思路前缀和数组也能做到 O(L)除了滑动窗口区间统计问题还可以用前缀和解决思路是这样的把 s 转成一个 0/1 数组 arrarr[i] 1 表示 s[i] 是 G 或 C否则为 0预处理 prefixprefix[i] 表示 arr[0] 到 arr[i-1] 的和区间 [i, ik-1] 的 GC 数量就是 prefix[ik] - prefix[i]遍历所有起点 i找到差值最大的第一个位置。两种方案复杂度一样差别在于滑动窗口省空间前缀和更好理解和验证。我建议两个都写一遍亲手写完会对区间统计这件事理解得更扎实。对比维度暴力枚举滑动窗口前缀和单窗口统计成本O(k)O(1)O(1)整体时间复杂度O(L*k)O(L)O(L)额外空间O(1)O(1)O(L)实现难度低中中推荐使用场景对拍验证机考首选多次查询任意区间3. 三种主流语言的完整实现与高频易错点3.1 Python 实现读写组合与管理切片边界import sys def solve(): data sys.stdin.read().strip().split() if not data: return s data[0] k int(data[1]) L len(s) if k 0 or k L: print() return cnt 0 for i in range(k): if s[i] G or s[i] C: cnt 1 max_cnt cnt ans_start 0 for i in range(1, L - k 1): if s[i - 1] G or s[i - 1] C: cnt - 1 if s[i k - 1] G or s[i k - 1] C: cnt 1 if cnt max_cnt: max_cnt cnt ans_start i print(s[ans_start:ans_start k]) if __name__ __main__: solve()Python 最容易翻车的不是滑窗逻辑而是输入读取。华为机考的输入有时第一行字符串、第二行整数有时语义上其实是同一行用空格分隔有时还有多余空行。如果你用s input().strip()然后k int(input().strip())遇到同一行输入ACGT 2就会出问题。稳妥写法是用sys.stdin.read().split()把所有 token 读进来再按顺序取。另外注意 Python 切片的右边界是开区间。取子串时写成s[ans_start:ans_startk]不是ans_startk-1。第一次写的人经常在这个地方困惑调试时多打印几个 i 和窗口内容就明白了。3.2 C 实现while 循环读取多组用例#include iostream #include string using namespace std; bool isGC(char c) { return c G || c C; } int main() { string s; int k; while (cin s k) { int L s.size(); if (k 0 || k L) { cout endl; continue; } int cnt 0; for (int i 0; i k; i) { if (isGC(s[i])) cnt; } int maxCnt cnt; int start 0; for (int i 1; i L - k; i) { if (isGC(s[i - 1])) --cnt; if (isGC(s[i k - 1])) cnt; if (cnt maxCnt) { maxCnt cnt; start i; } } cout s.substr(start, k) endl; } return 0; }C 中while (cin s k)是应对多个测试用例的标准写法。读入成功后进入循环没有更多输入时cin 返回 false自然退出。如果只写了一次读入而没有 while遇到多组数据时只会处理第一组剩下全丢。另外要注意substr的语义第一个参数是起始位置第二个参数是长度不是结束位置。所以s.substr(start, k)正好截取从 start 开始长度为 k 的子串。有些人写成s.substr(start, start k)数据一大就出问题。3.3 Java 实现Scanner 的陷阱与 substring 的区间语义import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNext()) { String s sc.next(); int k sc.nextInt(); int L s.length(); if (k 0 || k L) { System.out.println(); continue; } int cnt 0; for (int i 0; i k; i) { char c s.charAt(i); if (c G || c C) cnt; } int maxCnt cnt; int start 0; for (int i 1; i L - k; i) { if (s.charAt(i - 1) G || s.charAt(i - 1) C) cnt--; if (s.charAt(i k - 1) G || s.charAt(i k - 1) C) cnt; if (cnt maxCnt) { maxCnt cnt; start i; } } System.out.println(s.substring(start, start k)); } } }Java 用while (sc.hasNext())读取多组用例需要注意避免在nextInt()后直接跟nextLine()的经典错误。nextInt()不会吃掉换行符紧接着的nextLine()读到的往往是空字符串字符串变量就会变成空壳。正确做法是统一用next()和nextInt()它们会自动跳过空白字符。还有类名必须是Main否则判题系统直接编译错误。我见过有人在自己电脑上叫DNA复制上去也不改白丢一道题。这个细节不检查真的能让人当场崩溃。3.4 三个公认翻车点边界、等于号和字符类型翻车点错误写法正确做法更新条件if (cnt maxCnt)用保证同分取第一个窗口右边界循环到L-k1导致越界循环到L-k访问s[ik-1]字符判断s[i] G或s[i] g用单引号G、C必要时先转大写用的后果是后面出现同样数量 GC 的子串会覆盖最早的那个输出不是题目要求的答案。同分取最早这类条件几乎所有题都是写严格大于。边界问题最隐蔽。如果 k 刚好等于 L只有一个窗口滑窗循环根本不会执行直接输出第一个窗口此时初始化代码必须正确。如果 k 大于 L则在任何数组访问之前就要拦截住输出空结果。Python 里s[i]是长度为 1 的字符串和G比较没问题但和GC比较就会永远 False。写的时候要保持类型一致别混用。4. 华为机考判题环境输入格式、时限与答题顺序4.1 牛客的 ACM 模式和 LeetCode 的函数签名模式完全不同华为机考用的是牛客网系统不是 LeetCode 的在线 IDE。LeetCode 会给好函数签名你只需要实现一个函数返回结果牛客需要自己写完整程序从标准输入读数据用标准输出打印结果。这个差异我见过太多人栽过。平时刷 LeetCode 习惯了到机考上看到输入描述输出描述第一反应居然是找类名和方法名。所以在机考前一定要做三件事把常见输入处理模板练熟字符串、整数、数组单组、多组用你熟悉的语言各写一遍确认类名或文件名要求Java 提交时类名必须 MainPython 文件名无所谓但 C 的 main 函数返回类型必须是 int不要在代码里写任何文件读写牛客系统已经把输入接到标准输入流你只从标准输入读即可。4.2 时限和数据结构的选择华为机考的判题环境对 C/Java 的时限通常比较紧Python 会有一定放宽。以 DNA 序列的数据范围来说如果 L 在 10^4 以内Python 滑动窗口几毫秒就能跑完完全没有压力但如果用暴力就可能卡在某个隐藏的大数据点上。因此建议即便用 Python也首选滑动窗口不要因为这题简单就轻视复杂度。内存方面256MB 基本够用前缀和数组也就 L1 个整数完全不会超。真正需要注意的是不要在循环体内不断创建切片比如每一轮都写sub s[i:ik]。Python 切片虽然快但在 O(L) 的循环里重复创建长字符串会带来不必要的内存和拷贝开销。正确做法是只记录最优起始位置 start最后输出时再切一次。4.3 先暴力还是先滑窗考试中的决策顺序如果你对滑动窗口已经很熟了当然直接写。但如果刚看到题心里没底可以这样决策第一遍先想暴力把暴力伪代码写在草稿纸上确认逻辑通顺再想想复杂度是否不可接受。机考不给你数据范围说明书默认按大数据准备如果对边界条件没有十足把握先提交一次暴力版本拿到一部分分再优化成滑动窗口。华为机考对提交次数通常没有严格惩罚最终 AC 才是最重要的。更实际的经验是把时间优先分配给第一题因为第一题是保底分。如果某套题第一题就是 DNA 序列建议 15 分钟内解决。超过 20 分钟还卡着先写一版暴力交上去保底然后做后面的题有时间再回来优化。4.4 本地自测样例设计除了样例还要测这几种边界机考最常见的翻车是样例过了、隐藏用例全红原因就是只测了题面样例。以 DNA 序列为例提交前至少跑满这些用例场景输入期望输出标准样例ACGT / 2CG窗口等于全长ACGT / 4ACGT窗口小于 1ACGT / 0空窗口大于全长ACGT / 5空全是 A/TAAAA / 2AA字符串只有 G/CGGCC / 2GG多组输入ACGT 2 换行 GGCC 2CG 换行 GG这些用例不用全记关键是窗口长度等于全长窗口长度大于全长所有子串 GC 数量相同这三类它们能精准卡掉大部分边界 bug。5. 从 DNA 序列延伸到一类题固定窗口模板和变体5.1 抽一个可以直接套用的固定窗口模板function solve(s, k): if k 0 or k len(s): return cnt 统计 s[0:k] 中目标字符的个数 ansStart 0 for i 1 to len(s) - k: if s[i-1] 是目标字符: cnt-- if s[ik-1] 是目标字符: cnt if cnt 当前最优: 更新最优和 ansStart return s[ansStart : ansStart k]很多看起来完全不同的题最后都落回这个模板区别只在统计什么和最优怎么比统计窗口内不同字符数就是无重复字符的最长子串的窗口版本统计窗口内 0 的个数就是最大连续 1 的个数统计窗口内字符种类和数量就是字符串的排列。所以在学习时建议把滑动窗口当成一个统一专题来刷而不是一题一题孤立地记答案。5.2 变体一输出起始下标和输出比例有些题面问的不是子串而是起始下标这时候不要存子串直接存 start最后输出 start。如果题目要求输出 GC 比例并保留两位小数分母固定是 k你仍然可以先比较数量在输出时再算比例比如print(f{max_cnt / k:.2f})。一个容易踩的坑是如果题目要求输出比例但你只保存了最大数量而没有保存对应的起始位置后面想找子串内容就得重新截取。所以编码之前一定要想清楚最终要输出什么东西决定你的答案变量到底存子串、起始位置还是比例。5.3 变体二同分取字典序最小的子串如果题目改成比例最高且字典序最小比较逻辑会变复杂。滑动扫描时遇到 cnt 大于当前最优就无脑更新等于时还要比较s[i:ik]和当前答案的字典序。# 仅展示比较逻辑差异 if cnt max_cnt or (cnt max_cnt and s[i:i k] ans): max_cnt cnt ans s[i:i k]由于比较字符串是 O(k)最坏情况下整体复杂度退化到 O(L*k)。如果数据范围大需要用字符串哈希把比较优化到 O(1)但这已经超出华为机考第一题的难度。了解这个变体的意义在于提醒你做题前一定要细读多个答案如何处理这句话不同的约定对应完全不同的比较逻辑。5.4 变体三统计满足阈值的子串数量假如不是要最大而是问有多少个长度为 k 的子串GC 比例大于等于 0.5滑动窗口主体完全一样只是不再维护 maxCnt而是维护一个计数器 result。每移动一次窗口如果当前cnt * 2 k用整数乘法避免浮点等价于比例大于等于 0.5result。这个变体在工程上很常见比如统计过去 5 分钟内接口响应时间超过 500ms 的次数、统计单位时间内 CPU 负载超过阈值的窗口数量。理解了 DNA 序列这道题等于顺手掌握了这类区间统计 阈值判断的写法。5.5 同类题清单刷完一套思路别只刷一道固定窗口统计或者变长窗口统计的经典题目我整理了一批LeetCode 643子数组最大平均数 I固定窗口求区间和与 DNA 序列几乎一一对应LeetCode 438找到字符串中所有字母异位词固定窗口加字符频次数组LeetCode 567字符串的排列固定窗口加字符频次数组LeetCode 3无重复字符的最长子串变长窗口加哈希表LeetCode 76最小覆盖子串变长窗口加字符频次数组LeetCode 1004最大连续 1 的个数 III变长窗口加最多翻转几个 0。不需要全部刷完但刷完前三道之后你会形成条件反射看到连续子串 固定长度 最大/最小/计数第一反应就是滑动窗口。6. 实测踩坑记录为什么有人写了十分钟调了两小时6.1 案例把写成的反面我印象很深的一个案例是一个朋友第一次做这道题。样例 ACGT / 2 输出 CG本地对提交全错。他反复检查算法最后发现写的是if cnt maxCnt。当扫描完 AC、CG、GT 三个窗口时CG 和 GT 的 cnt 都是 2他用 GT 覆盖了 CG输出成了 GT。题面写的是输出最先出现的他正好漏了最先两个字。这个例子说明读题时圈出最先最长最短字典序最小这些关键词比多写十行代码都管用。细节决定成败真不是一句空话。6.2 案例输入读取出问题算法再对也没用另一个朋友用 Java 写把第一行字符串用sc.nextLine()读第二行用sc.nextInt()读。样例通过提交全红。原因是他本地的输入是ACGT换行2nextLine() 正常读到 ACGT可牛客有的用例是ACGT 2在同一行nextLine() 读到ACGT 2第二行 nextInt() 自然就没得读了直接异常。后来改成sc.next()加sc.nextInt()问题瞬间消失。所以读入格式不确定时尽量用按空白 token 读取而不是按行读取。6.3 案例明明过了样例却栽在 k 大于 L第三种情况是我自己踩的。当时把 k L 的情况忽略了因为样例里没有这种输入。机考隐藏用例里有一个字符串很短、窗口很长的测试点Python 代码直接进入循环后s[ik-1]虽然不会崩溃但会得到错误的结果C 版本则直接越界。从那以后我给自己定了一条规矩凡是涉及固定窗口的题第一行代码永远先检查合法性k 不在 [1, L] 范围内直接输出空结果。这条规矩后来救了我好几道题建议你也把它写进自己的代码习惯里。6.4 机考现场的心态建议最后说说心态。华为机考给的时间其实比较紧张但像 DNA 序列这种第一梯队的题答不出来基本上不是智力问题而是准备问题。我的建议是考试前把所有语言的标准输入输出模板写好、背熟考试时先做第一题做完立刻检查边界条件再提交遇到没思路的题别死磕先把会的题拿分平时刷题时培养用对拍验证的习惯暴力版和优化版一起跑随机数据。上面这些教训每一个都是真金白银换来的。我一直觉得机考最遗憾的不是难题不会而是简单题因为输入输出或者一个大于号写错白丢满分。反正我是吃过亏的希望你不用再吃一遍。
