最近在牛客网刷字符串题总是绕不开“字符串替换”这类看起来毫无难度的题目。题目描述通常很简单给定一个字符串把其中重复出现的字母替换成#第一次出现的字母保持不变。乍一看谁都会可真用 C 动手写的时候问题会一串一串冒出来大小写算不算重复数字和标点要不要管空格怎么读进来数组下标怎么会是负数这篇文章不打算只贴一段代码就交差我会把这道题从题意拆解到多种 C 实现再到常见踩坑点完整走一遍。无论你是刚学完 C 语法的小白还是准备面试想快速过一遍基本功的人都可以顺着这里的思路自己敲一遍把字符串处理的基础打扎实。1. 题目理解与整体设计思路1.1 题意还原到底要对字符串做什么牛客网上的“字符串替换”题不同版本细节略有差别但核心规则基本一致把字符串中首次出现的字母保留之后再次出现的相同字母统一替换为字符#。注意这里的关键词是“相同字母”不是“相同字符”。如果题目只限定字母那数字、空格、标点符号都应该原样保留。把需求拆开看实际上要做两件事。第一遍历字符串的每一个字符判断它是不是需要被处理的字母第二判断这个字母在当前位置之前是否已经出现过如果出现过就改成#否则记录一下“这个字母已经出现了”。整个过程不需要对字符串做移位、不需要删除元素、不需要拼接新串只是做一次“边扫描边修改”的操作。这道题之所以经典是因为它把几个基础能力揉在一起字符遍历、ASCII 码的数值运算、用数组做标记、以及原地修改字符串。很多更复杂的字符串题比如统计字符频率、判断字符是否重复、滑动窗口去重底层都会用到类似的思路。所以把这道题吃透比多刷十道简单字符串题都值。1.2 为什么“标记数组”是这道题的天然选择我第一次刷这道题的时候脑子里冒出来的想法很朴素每遇到一个字母就往回扫描一遍看前面有没有出现过。比如字符串abcabc处理第4个字母a时需要回头看前3个字符里有没有a。这么做当然也能跑但如果字符串长度是 n最坏情况下每个字符都要往回扫 n 次时间复杂度退化到 O(n²)这就不是一个让人满意的解法。后来意识到题目要求的是“这个字母之前有没有出现过”天然适合用一个数组记录状态。因为英文字母一共就26个小写或52个分大小写我们可以开一个固定大小的数组数组下标对应字母编号数组的值标记“这个字母是否已经出现”。遍历字符串时先查标记数组如果是第一次出现就置为1否则就把当前字符替换成#。用生活里的场景类比这就像酒店前台登记入住的客人。前台小姐姐拿一份名单来一位客人先查名单没登记过就在名单上打个勾然后放行已经登记过了就告诉他“您已经来过了请去门牌号为#的房间”。整个流程只要扫一遍客人列表不需要每次都回头问前面的客人。这就是典型的空间换时间用一个固定大小数组的 O(1) 空间换来了 O(n) 的线性时间复杂度。1.3 两个容易混淆的规则大小写与字符范围动手写代码之前必须先把题目规则确认清楚否则写完了也是白写。我遇到过两个最容易出问题的点。第一个是大小写是否区分。有的题目认为 a 和 A 是同一个字母也就是大小写不敏感有的题目则认为它们是两个字符必须分开统计。如果题目描述里写“相同的字母”通常要看看样例再判断。比如相同输入aA不区分大小写的输出是a#区分大小写的输出是aA两个人答案完全不同测试点直接判错。第二个是替换范围。题目到底是说“把重复出现的字母替换成#”还是“把重复出现的字符替换成#”前者只处理 a-z 和 A-Z遇到数字、空格、标点一律跳过后者范围就广了所有可见字符包括数字、空格都可能被替换。我见过不少人在这一点上栽跟头明明题目只说字母结果代码里把空格也处理了输出自然不对。所以在读题阶段我建议先把这两点圈出来再动手写思路。牛客网有些题的描述写得比较简略实在拿不准的时候用题目给出的样例去推断规则或者直接按最常见的“只处理字母、大小写不敏感”来写并在注释里写明你的假设。2. 核心细节解析与 C 实现要点2.1 ASCII 映射原理字符和数组下标是怎么换算的C 里的字符类型 char 本质上是一个占用1字节的整数存储的是该字符在 ASCII 编码表中对应的数值。比如小写字母 a 的 ASCII 码是97z 是122大写字母 A 是65Z 是90。这意味着我们可以拿字符直接做算术运算把字母映射到数组下标。具体来说s[i] - a会把一个小写字母映射到 0 到 25 之间的整数a 映射到0b 映射到1以此类推。同理s[i] - A可以把大写字母映射到0到25。有了这个映射标记数组就能设计成int seen[26]每个位置对应一个字母。如果题目是大小写不敏感大写和小写字母应该复用同一个下标。常见做法是先把字符统一转成小写再减 a或者在小写分支用s[i] - a在大写分支用s[i] - A因为这两个计算对同一个字母得到的结果是一样的。例如l 和 L 都会映射到下标11所以后面的l 或 L 都会被当作重复字母处理。这里有个非常容易出现的问题如果不对字符做范围判断直接拿一个字符去减 a有可能得到负数或者超过25的整数。比如拿空格ASCII 码32减97结果是 -65用它做数组下标访问seen[-65]程序运行时会访问到数组之外的内存轻则结果错误重则直接崩溃。所以进行下标换算之前必须先确认ch a ch z或者ch A ch Z。2.2 C 风格数组和 std::string 两种载体怎么选牛客网上的老题很多保留了 C 语言风格的输入输出方式char 数组可以直接配合 scanf、printf 使用修改也直观。C 风格数组的写法会更靠近底层适合想复习指针和数组基本功的读者。#include stdio.h #include string.h void replaceString(char* s) { int len strlen(s); int seen[26] {0}; for (int i 0; i len; i) { if (s[i] a s[i] z) { int idx s[i] - a; if (seen[idx]) { s[i] #; } else { seen[idx] 1; } } else if (s[i] A s[i] Z) { int idx s[i] - A; if (seen[idx]) { s[i] #; } else { seen[idx] 1; } } } } int main() { char s[100] {0}; scanf(%s, s); replaceString(s); printf(%s\n, s); return 0; }std::string 则更符合现代 C 的写法用 getline 可以很方便地读取包含空格的整行输入遍历和修改也简洁。牛客的在线评测环境一般支持 C11 或 C14使用 std::string 完全没有问题。#include iostream #include string using namespace std; void replaceString(string s) { int seen[26] {0}; for (char c : s) { if (c a c z) { int idx c - a; if (seen[idx]) c #; else seen[idx] 1; } else if (c A c Z) { int idx c - A; if (seen[idx]) c #; else seen[idx] 1; } } } int main() { string s; getline(cin, s); replaceString(s); cout s endl; return 0; }我个人的建议是两种写法都要会。如果目标是把题目快速 AC用自己最熟的那一种就好如果是想锻炼 C 功底就刻意把两种都写一遍感受一下指针遍历、迭代器遍历、范围 for 循环之间的差异。2.3 原地修改字符串的边界问题这道题通常要求修改原字符串并输出而不是生成一个新的字符串返回。所以我们要直接在传入的字符数组或 string 对象上进行操作。原地修改有几个细节值得注意。第一不能用字符串字面量作为输入。比如const char* p abcabc;这种写法在 C 里是一个只读的字符串常量往p[3]写值属于未定义行为程序可能崩溃。牛客的输入一般是先读到 char 数组里数组是可写的所以这一步通常没问题。但如果自己本地测试千万别用字符串字面量去替代可写数组。第二替换成 # 不会截断字符串。因为 # 的 ASCII 码不是0替换之后只是把原来的字母变成了井号字符串的结尾符 \0 还在原来的位置所以打印时能正常输出完整内容。这里要小心别把第一次出现的字母误改成 \0那样字符串会被提前截断输出就少了一段。第三string 对象在修改时长度不会变化因为我们只是逐字符替换不涉及插入、删除所以迭代器不会失效。但要注意在 C 里对 string 使用下标访问时最好先把长度存下来避免每次循环都调用 size() 方法虽然这点性能损耗在这道题里几乎可以忽略但养成好习惯总没错。3. 实操过程与核心环节实现3.1 基础实现只处理字母大小写不敏感先给一个贴合牛客常见题意的版本只处理英文字母大小写不敏感非字母字符原样保留。代码的思路很清晰单个循环就能完成。#include stdio.h #include string.h void replaceString(char* s) { int len strlen(s); int seen[26] {0}; for (int i 0; i len; i) { if (s[i] a s[i] z) { int idx s[i] - a; if (seen[idx]) { s[i] #; } else { seen[idx] 1; } } else if (s[i] A s[i] Z) { int idx s[i] - A; if (seen[idx]) { s[i] #; } else { seen[idx] 1; } } } } int main() { char s[100] {0}; scanf(%s, s); replaceString(s); printf(%s\n, s); return 0; }这个版本里有几个刻意设计的点。首先seen[26]声明为 int 数组值是0或1用来表示某个字母是否出现过。其次大写和小写字母共用同一个 seen 数组这就是大小写不敏感的实现方式。最后else if 的写法保证每个字符只进入一个分支字符本身就是大写或小写之一不会同时处理两次。提示如果你不确定题目是否区分大小写可以先用这个大小写不敏感的版本提交看看如果某些测试点没过再改成区分大小写的版本。根据我在牛客上的经验很多字符串替换题确实是大小写不敏感的但一定要以题目样例为准。3.2 进阶实现用 ASCII 码作下标的通用去重写法如果题目要求不是“只处理字母”而是“把所有重复出现的字符都替换为#”那么开一个bool seen[128]会更合适。直接用字符的 ASCII 码作为数组下标数字、标点、字母统统可以被记录代码更短思路也更通用。#include stdio.h #include string.h void replaceString(char* s) { int seen[128] {0}; int len strlen(s); for (int i 0; i len; i) { unsigned char ch (unsigned char)s[i]; if (seen[ch]) { s[i] #; } else { seen[ch] 1; } } } int main() { char s[100] {0}; scanf(%s, s); replaceString(s); printf(%s\n, s); return 0; }注意到这里用了unsigned char类型转换。之所以这样做是因为某些平台上的 char 类型默认是 signed当字符串中出现 ASCII 码大于127的扩展字符时s[i]作为数组下标可能是负数导致访问越界。转成 unsigned char 后下标范围能正确覆盖 0 到 255。虽然牛客的普通测试一般不会出现扩展字符但写成这样更稳。同样地std::string 版本也可以用同样的思路配合getline读取可能有空格的整行字符串。#include iostream #include string using namespace std; int main() { string s; getline(cin, s); int seen[128] {0}; for (int i 0; i (int)s.size(); i) { unsigned char ch (unsigned char)s[i]; if (seen[ch]) { s[i] #; } else { seen[ch] 1; } } cout s endl; return 0; }有的同学可能会想用std::map或者std::set来做但这道题完全没有必要。map 内部是红黑树插入和查找的时间复杂度是 O(log n)性能不如数组unordered_set 虽然平均 O(1)但哈希函数有额外开销。定长数组是最轻量、最直接的选择这也算是一种“在合适场景选择合适的工具”的思维方式。3.3 测试用例与输出对比写完代码不能直接交一定要自己构造几组用例测一测。针对不同的题目规则我列了一张对比表方便你看清楚规则差异会造成什么影响。输入字符串题目规则期望输出Hello World只处理字母不区分大小写He#lo W#r#dHello World只处理字母区分大小写He#lo Wor#d1123abcabc只处理字母1123abc###1123abcabc所有重复字符#123abc###空字符串任意规则空以Hello World为例不区分大小写时第一个 l 保留后面的 l 和 L 如果出现都会被替换大写 W 因为是第一次出现所以保留后面再次出现的 o 会被替换成 #。而区分大小写时小写 o 和大写 O 互不影响所以第二组结果不同。这些用例在本地跑通之后再提交到牛客网心里就有底了。我习惯在本地多写几组极端用例比如长度只有1的字符串、全是同一个字母的字符串、字母夹杂数字的字符串比直接提交然后靠评测结果反馈要高效得多。3.4 复杂度分析和优化空间这道题的时间复杂度很容易分析只需要从头到尾遍历一次字符串每次循环内做常数次判断和数组访问所以是 O(n)n 是字符串长度。空间复杂度方面标记数组是固定大小不随输入规模变化所以是 O(1)。如果硬要计算char 数组本身是题目输入的一部分不算额外空间。那么还有没有优化空间从复杂度上看已经没有什么可优化的了。任何“判断重复”的问题都至少需要扫描一遍输入否则无法知道后面的字符在之前是否出现过。所以 O(n) 时间、O(1) 额外空间的解法就是这个问题的理论最优解。不过代码层面还有可以微调的地方。如果你写的是 C 风格版本可以尝试用指针遍历代替数组下标遍历比如char* p s; while (*p) { ... p; }这样能少一次strlen的扫描因为你是边移动指针边判断是否到结尾。对这道题来说这个优化收益微乎其微但作为 C 语言功底的练习值得试试。如果你用的是 std::string也可以试试用迭代器或者范围 for 循环感受不同遍历方式写起来有什么区别。4. 常见问题与排查技巧实录4.1 输入方式不对导致字符串只处理了一半这是我在牛客评论区里见过最多的问题。很多新手用scanf(%s, s)读字符串如果测试数据里包含空格比如Hello Worldscanf 只读到Hello就停住了空格和后面的World都留在缓冲区里代码处理的实际上是Hello。解决思路要看具体情况。如果题目保证输入不含空格那scanf(%s, s)简单又高效。如果输入可能包含空格C 语言可以用scanf(%[^\n], s)来读取一整行或者用cin.getline(s, 100)。std::string 的话直接用getline(cin, s)最合适。注意gets函数在 C11 标准里已经被移除了牛客的编译器如果用 C11 或更高版本提交包含gets的代码很可能编译失败。老旧教材里经常出现gets刷题时建议改用fgets或cin.getline。4.2 非字母字符被错误替换结果和答案对不上如果题目只说“把重复出现的字母替换成#”那么代码里必须对字符做范围判断。我见过直接把seen[128]方案用在“只处理字母”题目上的读者结果空格、数字也全变成 # 了输出自然不对。反过来如果题目说“把重复出现的字符都替换成#”那你只需要判断字符是否出现过不需要关心它是不是字母。最稳妥的办法是读题时把“字母”两个字圈出来代码里写成if (s[i] a s[i] z)或者if (s[i] A s[i] Z)这样的范围判断。4.3 数组越界、野指针和运行时错误这道题虽然简单但运行时错误RE并不少见。最常见的原因是直接拿字符减 a 得到的下标是负数然后访问了数组的越界位置。比如输入一个数字 1它的 ASCII 码是4949 - 97 -48访问 saw[-48] 就会出事。排查这类问题我一般先打印每个字符的 ASCII 码看看程序实际处理的数据长什么样。比如临时在循环里加一句printf(%d %c\n, s[i], s[i]);一旦发现某个字符在做减法之前没有满足字母判断条件问题就定位了。另一个技巧是使用 vector 的at()方法访问元素它会在越界时抛出异常方便本地调试定位完再改回数组下标即可。还有一种情况是字符串数组开得太小。牛客的题目如果没说明长度限制你可以预估一下但保险起见开char s[1000]甚至更大的长度避免读入数据超过数组大小。如果你用 std::string 就不存在这个问题这也是我推荐在刷题时多用 string 的原因之一。4.4 牛客网提交的几个实际细节牛客网的在线评测环境和本地 IDE 有些细微差别提交通常需要注意几点。第一main 函数最后要return 0;很多新手会漏掉虽然某些编译器能过但最好还是按标准写。第二如果题目要求“多组测试数据”不要只处理一组就返回需要使用 while 循环不断读入直到输入结束。第三尽量不要依赖#include bits/stdc.h这个万能头文件虽然牛客支持但它不是标准头文件换到其他平台可能编译失败老老实实包含iostream、string、stdio.h更稳妥。还有一个经验之谈提交后如果答案错误别急着改代码逻辑先看错误用例。牛客有些题目会在“错误提示”里给出你输出和期望输出的对比这是最快的定位方式。如果只显示“答案错误”而没有用例那就自己多造几组边界测试比如全重复、无重复、空字符串、大小写混合逐一验证。最后分享一个我从这道题里得到的习惯刷题时不要只看代码能不能过而是要有意识地把同一个问题用不同方法各写一遍。字符串替换这道题用 C 风格数组写一遍再用 std::string 写一遍然后变形成“大小写敏感”和“所有重复字符”的版本总共只需要半小时左右但你会对字符判断、标记数组、输入读取这些基础能力产生肌肉记忆。下次再遇到“判断字符是否重复”“统计字符频率”之类的题你会在第一时间想到这棵技能树这就是把简单题吃透的价值。