字符串处理实战：逆序、分割、比较与转换的C++刷题复盘

刷题的朋友应该都有这种体验动态规划会卡你三天二叉树会让人怀疑人生但字符串题目看起来总是人畜无害——直到你在细节上反复挨打。代码随想录刷到 Day4主题正好就是字符串这一天涵盖的内容逆序、查找、替换、分割、比较、转换再加上回文、排序这类综合应用几乎把日常开发里能碰到的字符串场景全部串了一遍。这篇笔记是我刷完 Day4 之后整理的复盘不是课程内容的复述而是把当天练习里涉及的技术点、边界条件和踩坑记录汇在一起。它适合刚开始刷算法题、或者写字符串问题时总在细节上翻车的朋友参考。下面所有示例以 C 为主同时会对比 Java、Python、C#、SQL 等场景里对应的写法因为字符串处理这件事语言会变底层思路是通的。1. 字符串与字符数组先把底层搞清楚再动手1.1 字符串不是数组是一段带结束标记的内存很多人在字符串题目上翻车根本不是逻辑问题而是没搞清字符串在内存里到底长什么样。C 语言里没有 string 这个类型只有char数组和char指针任何字符串字面量比如abc实际在内存中是 4 个字节a、b、c、\0。这个\0就是 C 字符串的结束符。新手第一个翻车点就在这里。strlen(abc)返回 3因为它数到\0就停了但sizeof(abc)返回 4因为sizeof统计的是整个字面量占用的空间连结束符一起算。声明char s[10] hello;时数组实际用了 6 个字节最后一个是结束符前面 5 个是字符。搜索里经常出现cstring字符串结束符这个词背后问的基本就是这些。C 的std::string则完全不用关心结束符它内部维护长度信息调用size()或length()就是真实字符数。好处是不用手动处理\0但坏处是有些人写惯了 C会在 C 里写出strlen(s.c_str())这种多此一举的代码。除非要调 C 接口否则没必要把std::string转成 C 字符串。再说初始化。c字符串数组初始化这个搜索词也很高频。常见的姿势有这几种string arr1[3] {aa, bb, cc}; // string 数组 vectorstring arr2 {aa, bb, cc}; // vector 动态数组最推荐 char arr3[3][20] {aa, bb, cc}; // C 风格二维字符数组 const char* arr4[] {aa, bb, cc}; // 指针数组存放字符串最后一种要特别小心指针数组里存放的是字符串字面量字面量在 C 里通常是只读的arr4[0][0] x这种修改是未定义行为在某些编译器上会直接崩溃。如果只是读取指针数组没问题如果后续要改字符就用char二维数组或std::string。1.2 字符串可变还是不可变决定了你敢不敢改python字符串直接赋值更改这个搜索词很有意思它反映了一个非常普遍的误解。Python 里写s abc然后s def看起来像是直接赋值更改了字符串实际上 Python 的str是不可变对象第二次赋值是把变量s重新绑定到了一个全新字符串对象上原来的abc还在内存里躺着。如果你试图s[0] x解释器会直接抛TypeError。Java 和 C# 也一样字符串不可变。C 的std::string是可变的s[0] x完全合法。这一点对算法题影响很大因为不少题目要求原地修改字符串比如反转、替换空格等。如果语言本身不支持改字符串那就先转成可变的容器——Java 用toCharArray()Python 用list(s)处理完再转回去。这里有一个通用的思考顺序拿到字符串题目先问自己三个问题——当前语言的字符串可变吗题目要求原地操作还是允许新开空间单字符操作和子串操作的代价是否一样把这三个问题在脑子里过一遍很多低级错误就能避免。2. 逆序输出一个需求带出三套实现方案2.1 双指针原地逆序是最稳的写法字符串逆序大概是我见过的、出现频率最高的字符串需求之一面试、笔试、PTA 作业里都有。最简单的实现是 C 一行调用#include algorithm reverse(s.begin(), s.end());但如果题目要求手写或者你面试时需要展示思路双指针是必须能默写出来的void reverseString(string s) { int left 0; int right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }为什么用双指针因为它只需要遍历n/2次时间复杂度 O(n)空间复杂度 O(1)不依赖额外容器。而且这个思路可以扩展到很多变体题上比如反转链表、判断回文、翻转数组都是同一个框架。PTA 的字符串逆序 c 语言类题目通常不允许你调用现成库函数所以手写版本一定要熟练。2.2 递归和栈属于能写但要想清楚代价的方案递归逆序打印其实很优雅void printReverse(const string s, int idx) { if (idx s.size()) { return; } printReverse(s, idx 1); cout s[idx]; }每次递归先往后走回溯时再输出自然就是逆序。但它的缺点是递归深度等于字符串长度字符串很长时可能爆栈。面试时写递归没问题但要能说出空间复杂度是 O(n)因为系统栈在存每一层调用的状态。栈的思路同理把字符逐个入栈再逐个出栈输出顺序自然反转。这个方法的问题一样需要额外 O(n) 空间。日常开发里用不到算法题里也通常不是最优解但因为理解起来直观很多人喜欢拿它做思路铺垫。可以写但最终要落到双指针上。2.3 逆序但不完全逆序整句反转才是真正的考点还有一个高发场景不是让你反转整个字符串而是反转句子里的单词顺序比如I am a coder变成coder a am I。如果先整体反转再按单词边界局部反转就能原地完成。这是典型的两段式双指针应用。string reverseWords(string s) { reverse(s.begin(), s.end()); int n s.size(); int start 0; while (start n) { while (start n s[start] ) start; int end start; while (end n s[end] ! ) end; reverse(s.begin() start, s.begin() end); start end; } return s; }这个思路第一次见的人会觉得绕为什么先整体反转原因很简单——整体反转后单词的相对顺序反了但每个单词内部的字符也反了所以再对每个单词做一次局部反转单词内部就正回来了而单词之间的顺序已经完成反转。这个先整体、再局部的套路在字符串题目里很常见记下来能省不少事。3. 查找、替换与分割高频操作的三板斧3.1 判断包含最容易被有没有这个 API卡住字符串相关的日常操作里包含判断用得最多。C 里最常见的是findstring s hello world; if (s.find(world) ! string::npos) { // 找到了 }string::npos是一个极大值表示没找到。新手容易犯的错误是直接写if (s.find(world))这等于判断返回值是不是 0而find返回的是下标所以这种写法只在子串恰好从第 0 位开始时才成立。C20 之后有s.contains(world)写起来更直接。不同语言里判断包含的 API 差异很大我整理过一个对照表很实用语言/环境判断包含的写法备注Cs.find(sub) ! string::npos老版本通用Javas.contains(sub)/s.indexOf(sub) ! -1contains 底层就是 indexOfPythonsub in s最直观JavaScripts.includes(sub)注意大小写敏感Oracle SQLINSTR(s, sub) 0或LIKE %sub%数据库场景SQL ServerCHARINDEX(sub, s) 0注意参数顺序和 INSTR 是反的有朋友问安卓开发检索字符串中包含哪个字其实就是 Java 的contains或indexOf没什么特殊 API但要注意在循环里频繁调用时先判断空字符串别让空子串判断出脏结果。SQL 场景的包含判断则是另一套体系INSTR返回位置LIKE走通配符思路和编程语言一致只是语法不同。3.2 分割字符串strtok 虽然香但坑更多这个必须单独拿出来说。C 语言里的strtok()是分割字符串的经典函数char s[] a,b,c; char* p strtok(s, ,); while (p ! nullptr) { cout p endl; p strtok(nullptr, ,); }输出a、b、c看起来很好用。但strtok有三个大坑很多人踩过之后才长记性第一它会修改原字符串。分割时它会把分隔符位置改成\0原串的内容直接被破坏。如果后续还要用原串就只能先复制一份。第二它内部用静态变量保存当前状态不可重入。多线程环境或者在一个线程里交替处理两个字符串时结果会很诡异。想安全一点可以用strtok_r但那是平台相关函数移植性一般。第三连续分隔符会被直接跳过。比如a,,b用strtok只能得到a和b中间的空字段丢了可很多场景恰恰需要保留空字段。C 里更可控的方案是用stringstream配合getlinestring s aa,bb,cc; stringstream ss(s); string item; while (getline(ss, item, ,)) { // item 就是每个字段 }这个写法可以指定分隔符而且能保留空字段因为每次getline读到分隔符就停不会跳过空字符串。C# 里就更简单了str.Split(,)返回字符串数组Python 用str.split(,)也可以指定分隔符。字符串解析 / 分割 / 映射这种词背后其实是一个常见需求组合把一段结构化字符串解析成键值对。比如name:jack,age:18,score:90先按逗号分割成三组再按冒号分割成键和值存进 map。分割只是第一步映射才是目的。C 没有内置的split所以掌握getline这种写法是刚需。3.3 替换操作单字符和子串是不同的难度替换单个字符最粗暴也最直接s[pos] x。但替换子串就讲究了C 的string::replace签名是replace(pos, len, str)三个参数分别是起始位置、替换长度、替换内容。新手最容易搞错第二个参数写成replace(pos, str.length(), str2)这种想当然的写法——长度是原串中被替换掉的部分的长度不是新串的长度。实际开发里经常遇到的是把模板里的占位符替换掉这种场景下别痴迷于手写循环。JavaScript 的模板字符串就是为此设计的Hello ${name}比反复拼接加号优雅得多也不会出现漏掉空格的问题。还有一个容易忽略的场景是 ODBC 连接字符串本质上就是你拼出一段格式固定的字符串然后传给驱动。这类配置型字符串看起来不是算法题但一样存在顺序、转义、替换的坑掌握了字符串处理的基本功处理它们会顺手很多。4. 比较、大小写与类型转换边界条件最容易翻车的地方4.1到底比的是什么分语言才能说清字符串比较相等这个需求搜索热度一直很高因为不同语言的行为真的不一样。我直接说结论C 语言里两个char*用比较的是指针地址不是内容。判断内容相等必须用strcmp(s1, s2) 0。C 的std::string重载了可以直接比较内容放心用。但如果你拿const char*和std::string比较会走转换行为可能不合预期最好统一类型再比。Java 的比较引用equals()比较内容经典考察点。C# 的string是引用类型但重载成了内容比较行为接近值类型。Python 的比较内容is比较对象身份。有个简单粗暴的记忆方式先判断这门语言里字符串是值类型还是引用类型。值类型就是比内容引用类型要看有没有重载。写题之前先确认这一点能避免很多莫名其妙的错误。C 里手写字符串比较函数时别忘了一个细节比较的是字典序不是长度类似strcmp的返回值语义小于返回负数、等于返回 0、大于返回正数。4.2 大小写转换别再用减 32这种土办法大小写转换的题目里总有人喜欢写if (c A c Z) c 32。这个写法在 ASCII 下没问题但代码可读性差而且一旦处理宽字符或扩展字符集就容易翻车。标准做法是tolower和toupperfor (char c : s) { c tolower((unsigned char)c); }或者更简洁地用std::transformtransform(s.begin(), s.end(), s.begin(), ::tolower);这里有一个细节很多人不知道tolower、toupper、isalpha、isalnum这一族函数都要求参数是unsigned char或EOF。如果传入一个普通的char当它是负数时扩展 ASCII 字符通常如此行为是未定义的。所以稳妥写法是tolower((unsigned char)c)。有人搜java 判断字符串中是否不是字母和数字对应的是 Java 的Character.isLetterOrDigit(c)C 里则是isalnum。回文判断、过滤非法字符这类题目里几乎必用。注意判断条件别写反要只保留字母数字就判断isalnum为真要去除字母数字才判断为假。4.3 字符串与数字互转失败时的表现你必须知道字符串和数字互转也是超级高频需求。C 里推荐stoi和to_stringint n stoi(123); string s to_string(123);stoi转不了时会抛std::invalid_argument超出范围抛std::out_of_range。而 C 的atoi转换失败时返回 0你根本分不清输入是0还是abc。所以 C 里尽量别用atoi。C# 那边除了int.Parse还有int.TryParse不抛异常返回布尔值。SQL Server 转数字用CONVERT(int, col)或CAST(col AS int)Oracle 用CAST或TO_NUMBER。Qt 开发里 double 转字符串用QString::number(d, f, 2)可以指定小数位数比手动拼接靠谱。Python 操作 Excel 时经常遇到单元格值是数字但读出来是字符串的情况判断type(cell.value)再决定是否int()也是这类问题的变体。还有一个枚举类型转换为字符串的需求在 C 里没有内置支持。常见做法是拿数组或map做映射enum Color { RED, GREEN, BLUE }; string colorToString(Color c) { static const char* names[] {RED, GREEN, BLUE}; return names[c]; }C# 则直接提供Enum.ToString()。C 走手写映射是因为它没有反射机制枚举在运行时就是整数。这种数字转描述的套路本质上和字符串转换同源都是在做某种形式的to_string。5. 回文、排序与综合应用把操作串成题解5.1 回文判断双指针的另一个经典主场回文字符串是面试题里的常客判断一个字符串是否是回文双指针写法很直接bool isPalindrome(string s) { int left 0; int right s.size() - 1; while (left right) { while (left right !isalnum((unsigned char)s[left])) left; while (left right !isalnum((unsigned char)s[right])) right--; if (tolower((unsigned char)s[left]) ! tolower((unsigned char)s[right])) { return false; } left; right--; } return true; }这段代码解决了两件事一是跳过非字母数字字符比如逗号、空格、标点二是不区分大小写。如果没有这两个要求代码会短很多但凡是涉及忽略杂质的回文题这个模板可以直接套。注意isalnum和tolower我都强转了unsigned char这就是上一节说过的细节不转在某些输入下会出问题。5.2 字符串排序不只是字典序那么简单字符串排序有几种场景。单字符串内部排序sort(s.begin(), s.end())一行搞定按 ASCII/字典序排。字符串数组排序默认也是字典序。但在某些题目里排序规则不是默认的最典型的就是拼数问题。题目大概是这样的给定若干非负整数或字符串表示的数让你把它们拼接起来使得拼接后的结果最大。朴素做法会犯错直接按数字大小降序拼接不对。比如9和91数字大小是 91 大于 9但991大于919所以 9 应该排在 91 前面。正确做法是比较两个字符串拼接后的结果vectorstring nums {3, 30, 34, 5, 9}; sort(nums.begin(), nums.end(), [](const string a, const string b) { return a b b a; // 拼接后更大的排前面 });为什么这个规则有效因为a b和b a的字符数相同字典序比较就等价于数值比较而且这个比较关系在数学上满足排序所需的传递性所以直接交给sort即可。如果要求拼成最小数把比较符号反过来就行。这个套路第一次接触会觉得很妙想通了就发现本质是自定义比较器。5.3 频次统计与映射字符串题的隐藏主角很多字符串题目的本质是字符频次或分组最经典的统计方式是用固定大小数组int cnt[26] {0}; for (char c : s) { cnt[c - a]; }因为英文字母只有 26 个用下标映射很方便。如果字符串包含大写字母可以先统一转成小写或者开 52 大小。这个字符转下标的思路是判断字母异位词、找第一个不重复字符、计算字符串是否可由另一字符串重排得到等问题的共同基础。更复杂的场景会用哈希表做映射比如统计每个单词出现次数本质是分割 映射 计数的组合。你现在回头看第 3 章的分割和第 5 章的统计会发现它们不是孤立的知识点而是同一类题目的不同阶段。字符串题之所以综合性强就是因为这些基础操作经常要串在一起用。6. 打卡复盘Day4 常见的坑和我的纠错清单6.1 让我当场宕机的三个小坑第一个是单引号和双引号的区别。a是chara是const char[2]包含一个a加一个\0。有人写s[i] a编译直接报错因为左边是char右边是const char*压根不是同一个类型。比较单个字符就用单引号比较字符串就用双引号或string这个习惯越早养成越好。第二个是 Code::Blocks 里宽字符串L...相关的报错。不少初学者写wchar_t* w L你好;后用printf(%s, w)输出结果乱码或者编译警告。原因很简单L...是宽字符常量每个字符占多个字节%s是按窄字符处理的格式不匹配。要用wprintf(L%ls, w)或者wcout。如果你只是处理普通 ASCII 字符串根本不必加L前缀加了反而给自己找麻烦。第三个是 C 字符串可写性问题。char* p abc; p[0] x;这种行为是未定义的现代编译器下大概率崩溃。因为abc是字符串字面量可能被放在只读区。要想能修改得用数组形式char p[] abc;。一句话记住字面量是只读的数组是读写皆可的。6.2 通用自检清单写字符串题之前先过一遍刷完 Day4 之后我总结了一份自检清单每道字符串题写完都拿这些用例跑一遍错题率低了很多空字符串很多算法在空串上会出现越界或死循环。单个字符a双指针的 left 和 right 可能直接相等。全空格或全是分隔符比如 或,,,。末尾带分隔符比如a,b,看你的分割逻辑是保留尾部空串还是忽略。连续分隔符比如a,,bstrtok会跳过getline会保留按需求选。大小写混合判断回文时别忘了统一大小写。开头结尾有空格反转单词那道题的经典陷阱。数字里的 0字符串0和整数 0 混用时比较逻辑对不上。这些用例不是靠背的而是写题时自然积累出来的。遇到一次边界翻车就把它记到这个清单里下次写新题前过一遍比刷十道新题还有用。最后再分享一点个人体会。字符串算法题的核心不是奇技淫巧而是把内存里到底存了什么想清楚。只要能在大脑里画出那串字符的布局知道结束符在哪、分隔符在哪、空格在哪逆序、分割、比较、替换就全都顺理成章。后面的哈希表专题还会频繁用到字符串这些手感都会派上用场。给同样在刷题的朋友一个建议遇到字符串题先别急着写代码拿笔在草稿纸上把字符串的布局画出来再动手写逻辑你会发现自己少踩很多坑。