企业官网建设流程全解析

如果只能给准备华为机考的人推荐一道必刷题，我会毫不犹豫地说：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-k+1 个，每个子串统计要遍历 k 个字符，因此总时间复杂度是 O((L-k+1) * k)，最坏情况下约 O(L * k)。

有人会觉得字符串处理几千个字符，就算 O(L*k) 也没啥。但机考的评测数据不会只有一个小样例。假设 L 达到 10^4，k 取 5000，暴力就是 5000 万次基本操作。C++ 可能还撑得住，Python 在这种量级下跑满全部隐藏用例，超时的概率非常大。华为机考的 Python 时限一般比 C++ 宽，但不会无限宽。

而滑动窗口整体遍历一遍字符串，每个字符在进入窗口和离开窗口时各处理一次，总的操作是常数倍的 L，也就是 O(L)。从 O(L*k) 到 O(L)，这个优化不是抠常数，是真的降了一个数量级。

2.3 滑动窗口的直观理解：一扇移动的玻璃窗

你可以把长度为 k 的窗口想象成一扇玻璃窗，贴在字符串上。窗口在位置 i 时看到的内容是 s[i] 到 s[i+k-1]，挪一格，左边会走出一个字符，右边会走进一个字符，窗口内的其他字符原封不动。

所以维护一个变量 cnt 表示当前窗口里 G 和 C 的总数。窗口右移一格时，只需要处理两件事：

• 走出窗口的字符 s[i] 如果是 G 或 C，cnt 减 1；
• 走进窗口的字符 s[i+k] 如果是 G 或 C，cnt 加 1。

因为每次移动只处理两个字符，单次是 O(1)，整体是 O(L)。

需要特别注意的是，第一个窗口必须先手动初始化。比如 i=0 时的窗口是 s[0:k]，这个窗口的 cnt 要先用一个循环数出来，然后再让窗口开始滑动。很多人就是漏掉了第一步初始化，导致 max_cnt 初始值是 0，输出永远错误。别笑，这一步真的非常容易丢。

2.4 辅助思路：前缀和数组也能做到 O(L)

除了滑动窗口，区间统计问题还可以用前缀和解决，思路是这样的：

• 把 s 转成一个 0/1 数组 arr，arr[i] = 1 表示 s[i] 是 G 或 C，否则为 0；
• 预处理 prefix，prefix[i] 表示 arr[0] 到 arr[i-1] 的和；
• 区间 [i, i+k-1] 的 GC 数量就是 prefix[i+k] - prefix[i]；
• 遍历所有起点 i，找到差值最大的第一个位置。

两种方案复杂度一样，差别在于滑动窗口省空间，前缀和更好理解和验证。我建议两个都写一遍，亲手写完会对"区间统计"这件事理解得更扎实。

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_start+k]，不是ans_start+k-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 三个公认翻车点：边界、等于号和字符类型

用>=的后果是，后面出现同样数量 GC 的子串会覆盖最早的那个，输出不是题目要求的答案。"同分取最早"这类条件，几乎所有题都是写严格大于。

边界问题最隐蔽。如果 k 刚好等于 L，只有一个窗口，滑窗循环根本不会执行，直接输出第一个窗口，此时初始化代码必须正确。如果 k 大于 L，则在任何数组访问之前就要拦截住，输出空结果。

Python 里s[i]是长度为 1 的字符串，和'G'比较没问题，但和"GC"比较就会永远 False。写的时候要保持类型一致，别混用。

4. 华为机考判题环境：输入格式、时限与答题顺序

4.1 牛客的 ACM 模式和 LeetCode 的函数签名模式完全不同

华为机考用的是牛客网系统，不是 LeetCode 的在线 IDE。LeetCode 会给好函数签名，你只需要实现一个函数返回结果；牛客需要自己写完整程序，从标准输入读数据，用标准输出打印结果。这个差异我见过太多人栽过。平时刷 LeetCode 习惯了，到机考上看到"输入描述""输出描述"，第一反应居然是找类名和方法名。

所以在机考前，一定要做三件事：

• 把常见输入处理模板练熟，字符串、整数、数组，单组、多组，用你熟悉的语言各写一遍；
• 确认类名或文件名要求，Java 提交时类名必须 Main，Python 文件名无所谓，但 C++ 的 main 函数返回类型必须是 int；
• 不要在代码里写任何文件读写，牛客系统已经把输入接到标准输入流，你只从标准输入读即可。

4.2 时限和数据结构的选择

华为机考的判题环境对 C++/Java 的时限通常比较紧，Python 会有一定放宽。以 DNA 序列的数据范围来说，如果 L 在 10^4 以内，Python 滑动窗口几毫秒就能跑完，完全没有压力；但如果用暴力，就可能卡在某个隐藏的大数据点上。因此建议即便用 Python，也首选滑动窗口，不要因为"这题简单"就轻视复杂度。

内存方面，256MB 基本够用，前缀和数组也就 L+1 个整数，完全不会超。真正需要注意的是不要在循环体内不断创建切片，比如每一轮都写sub = s[i:i+k]。Python 切片虽然快，但在 O(L) 的循环里重复创建长字符串会带来不必要的内存和拷贝开销。正确做法是只记录最优起始位置 start，最后输出时再切一次。

4.3 先暴力还是先滑窗：考试中的决策顺序

如果你对滑动窗口已经很熟了，当然直接写。但如果刚看到题心里没底，可以这样决策：

• 第一遍先想暴力，把暴力伪代码写在草稿纸上，确认逻辑通顺；
• 再想想复杂度是否不可接受。机考不给你数据范围说明书，默认按大数据准备；
• 如果对边界条件没有十足把握，先提交一次暴力版本，拿到一部分分，再优化成滑动窗口。华为机考对提交次数通常没有严格惩罚，最终 AC 才是最重要的。

更实际的经验是：把时间优先分配给第一题，因为第一题是保底分。如果某套题第一题就是 DNA 序列，建议 15 分钟内解决。超过 20 分钟还卡着，先写一版暴力交上去保底，然后做后面的题，有时间再回来优化。

4.4 本地自测样例设计：除了样例，还要测这几种边界

机考最常见的翻车是样例过了、隐藏用例全红，原因就是只测了题面样例。以 DNA 序列为例，提交前至少跑满这些用例：

这些用例不用全记，关键是"窗口长度等于全长""窗口长度大于全长""所有子串 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[i+k-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:i+k]和当前答案的字典序。

# 仅展示比较逻辑差异 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.5），result++。

这个变体在工程上很常见，比如统计过去 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换行2，nextLine() 正常读到 ACGT；可牛客有的用例是ACGT 2在同一行，nextLine() 读到ACGT 2，第二行 nextInt() 自然就没得读了，直接异常。

后来改成sc.next()加sc.nextInt()，问题瞬间消失。所以读入格式不确定时，尽量用按空白 token 读取，而不是按行读取。

6.3 案例：明明过了样例，却栽在 k 大于 L

第三种情况是我自己踩的。当时把 k > L 的情况忽略了，因为样例里没有这种输入。机考隐藏用例里有一个字符串很短、窗口很长的测试点，Python 代码直接进入循环后，s[i+k-1]虽然不会崩溃，但会得到错误的结果；C++ 版本则直接越界。

从那以后，我给自己定了一条规矩：凡是涉及固定窗口的题，第一行代码永远先检查合法性，k 不在 [1, L] 范围内直接输出空结果。这条规矩后来救了我好几道题，建议你也把它写进自己的代码习惯里。

6.4 机考现场的心态建议

最后说说心态。华为机考给的时间其实比较紧张，但像 DNA 序列这种第一梯队的题，答不出来基本上不是智力问题，而是准备问题。我的建议是：

• 考试前把所有语言的标准输入输出模板写好、背熟；
• 考试时先做第一题，做完立刻检查边界条件，再提交；
• 遇到没思路的题别死磕，先把会的题拿分；
• 平时刷题时培养用对拍验证的习惯，暴力版和优化版一起跑随机数据。

上面这些教训每一个都是真金白银换来的。我一直觉得机考最遗憾的不是难题不会，而是简单题因为输入输出或者一个大于号写错，白丢满分。反正我是吃过亏的，希望你不用再吃一遍。