★ FEATURED ARTICLE 说来也巧前几天我帮一位朋友做模拟面试他三分钟就把“反转字符串”写完了我随口问了一句reverse函数里为什么用两个指针移动而不是数组下标他明显一愣。再追问“字符串在内存里到底长什么样”他开始在纸上画了一个大括号里面写了个s。说实话这类题挂得很冤枉——代码明明能跑但面试官想看的不是你背下来的解而是你脑袋里有没有那幅内存图。剑指 Offer 里字符串和指针相关的题考察的就是 C/C 基本功里最本质的部分字符数组怎么存、指针怎么移动、边界怎么收。这篇文章我把这套经典题的代表解法拆开讲再把背后的系统知识一次性梳理清楚。适合准备 C/C 岗位校招、社招也适合写嵌入式、客户端、后端但平时用 STL 用多了、想回头补一补基础的朋友。1. 先把字符串和指针的底层关系理清1.1 C 字符串的真实长相很多同学写 C 几年但问他“字符串是什么”答案往往是“char 数组”或者“char*”。这两个说法都不算错但都不完整。准确地说C 里没有原生字符串类型字符串是用char数组承载的并且以空字符\0作为结束标记。举个例子char str[] hello;这一行代码真正做的事情是在栈上申请一块 6 字节的内存依次存h,e,l,l,o,\0。str这个名字代表的是这块内存的首地址也就是第一个字符h的地址。所以“字符串”这个词实际上是一段连续内存 一个终止符的合称。而指针是什么指针变量存的是一个地址。char* p str;意思是p里存的是str首元素的地址p 1指向ep 5指向\0。字符串指针题的绝大多数考点都落在“指针移动”和“地址比较”上不是你想的语法背诵题。1.2 为什么面试官总爱出字符指针题面试官爱出这类题是因为它们能同时考察三件事你对内存布局的理解、你对边界条件的把握、你对“指针就是地址”这件事是否真的信了。内存布局char[]、char*指向常量区、函数返回局部数组分别存在哪里边界条件反转字符串时指针到\0应该停在哪儿替换空格时新字符串末尾是不是忘了补\0指针语义比较字符串内容为什么不能用数组名什么时候退化成指针参数里写char s[]和char* s等价吗可以说字符串指针题是最便宜的“基本功探测器”。一道简单的题能问出一个人平时写代码是靠直觉还是靠理解。1.3 一套自洽的排查规则我刷这类题时习惯在心里先过一套固定流程入参是否可能为NULL处理不处理先想清楚。字符串是否以\0结尾如果题目说的是“字符数组”而不是“字符串”那可能没有终止符一切 strlen 相关操作全部失效。操作是否越界复制时目标缓冲区容量够不够替换时新长度有没有多算一帧\0。指针移动要不要提前终止双指针题经常用pBegin pEnd代替pBegin ! pEnd避免奇数长度时两个指针交错越过。下面所有题解都是围绕这套规则展开的。2. 高频题解一替换空格与反转类题目的核心思路2.1 替换空格为什么大家统一推荐“从后往前”题面很经典给定一个字符数组原题假设空间足够把其中的空格替换成%20要求原地修改。最自然的想法是从前向后扫描遇到空格就把后面所有字符后移 3 格。但这样每次替换都涉及大量移动时间复杂度会退化到 O(n²)。更好的做法是先统计空格数量计算出新串长度然后从后往前复制void replaceBlank(char str[], int capacity) { if (str NULL || capacity 0) { return; } int originalLength 0; int blankCount 0; while (str[originalLength] ! \0) { if (str[originalLength] ) { blankCount; } originalLength; } int newLength originalLength blankCount * 2; // %20 比空格多 2 个字符 if (newLength capacity) { // 必须留出 \0 的位置 return; } int indexOfOld originalLength; // 从旧串末尾的 \0 开始 int indexOfNew newLength; // 新串末尾也是 \0 的位置 while (indexOfOld 0 indexOfNew indexOfOld) { if (str[indexOfOld] ) { str[indexOfNew--] 0; str[indexOfNew--] 2; str[indexOfNew--] %; } else { str[indexOfNew--] str[indexOfOld]; } indexOfOld--; } }关键点有两个。第一为什么从后往前因为替换是“把 1 个字符变成 3 个字符”后面的内容必须整体后移。从前往后写前面的新字符会覆盖尚未处理的老字符。从后往前则不存在这个问题——老位置永远在新位置前面写的过程中不会互相踩踏。第二很多人漏掉\0。老串末尾的终止符也要被搬过来它只占 1 格不需要替换成 3 格。代码里indexOfOld初始就是originalLength也就是\0所在的下标第一次循环就会把\0放到str[newLength]上。如果你从originalLength - 1开始最后就得手动补\0容易漏。顺带一提循环条件indexOfNew indexOfOld是剪枝当前面已经没有空格两个指针相遇时前面那段内容本来就在正确位置继续搬只是浪费时间。2.2 反转字符串双指针和对称交换反转一个字符串本质是把首尾两个字符交换然后向中间逼近void reverse(char* pBegin, char* pEnd) { if (pBegin NULL || pEnd NULL) { return; } while (pBegin pEnd) { char tmp *pBegin; *pBegin *pEnd; *pEnd tmp; pBegin; pEnd--; } }这个函数用指针而不是下标不是炫技而是因为后面的反转单词题需要复用它。传入str和str len - 1可以反整个字符串传入任意区间就能只反中间一段。pBegin pEnd这个条件同时兼容了奇偶长度奇数长度时中间那个字符最终会和自身相遇不交换就退出偶数长度时两指针交错之前退出。面试现场最容易出现的错误是pEnd指向了\0。记住str strlen(str)指向的是结束符不是最后一个有效字符。反转前要先pEnd--。2.3 翻转单词顺序一鱼两吃的经典套路题目通常是“I am a student.” 翻成 “student. a am I”。直接全反转行不行行但单词内部也会反转变成 “.tneduts a ma I”显然不对。标准解法是先整体反转再局部反转每个单词。整体反转之后单词内部的字符顺序是倒的把每个单词再反一次单词内容恢复正确单词之间的相对顺序已经被整体反转调换过了。char* reverseSentence(char* str) { if (str NULL) { return NULL; } char* pBegin str; char* pEnd str; while (*pEnd ! \0) { pEnd; } pEnd--; // 退到最后一个有效字符 reverse(pBegin, pEnd); pBegin str; pEnd str; while (*pBegin ! \0) { if (*pBegin ) { pBegin; pEnd; } else { pEnd pBegin; while (*pEnd ! \0 *pEnd ! ) { pEnd; } reverse(pBegin, pEnd - 1); // 反转当前单词 pBegin pEnd; } } return str; }这个写法的细节全在连续空格上。如果中间有多个空格pBegin会依次跳过空格单词识别逻辑不受影响。如果整个字符串全是空格循环会一直走到\0安全退出。反转时需要pEnd - 1而不是pEnd因为跳出 while 时pEnd停在了空格或\0上有效单词范围是[pBegin, pEnd-1]。左旋转字符串是同一套路。把“abcdefg”左旋两位得到“cdefgab”做法是反转[0, k-1]得 “bagfedc”反转[k, n-1]得 “bagfedc” 保持不变这里注意顺序标准做法是反转前 k 个、反转后 n-k 个、再整体反转或者先整体反转、再分别反转两段两种都能得到答案。原理相同反转两次能把内部顺序救回来同时达到交换两段位置的效果。3. 高频题解二字符串排列类题目的回溯与去重3.1 全排列的标准回溯框架字符串全排列是剑指 Offer 里典型的回溯题也是所有回溯题的入场券。核心思路是固定第一个位置穷举所有可能放到这个位置的字符固定第二个位置继续递归当所有位置都固定完输出当前序列。直接看交换法的实现void permutation(char* str, int start) { if (str NULL || start strlen(str)) { return; } if (start strlen(str) - 1) { printf(%s\n, str); return; } for (int i start; i strlen(str); i) { // 去重处理见 3.2 char tmp str[start]; str[start] str[i]; str[i] tmp; permutation(str, start 1); tmp str[start]; str[start] str[i]; str[i] tmp; // 回溯还原现场 } }回溯的两个关键动作是“进入下一步之前改状态”和“递归返回之后还原状态”。这里改的是字符串字符顺序所以递归完必须换回来否则同一层的后续迭代会在被破坏的排列上继续结果错乱。很多初学者以为回溯很难其实它就是一个带撤销的 DFS。记住“选择、递归、撤销”三连排列、组合、子集、N 皇后都是一套框架。3.2 含重复字符时的去重不能等全部生成完再查重题目如果是“对含有重复字符的字符串求全排列”比如“aab”照上面的代码会输出 6 个结果但实际上不重复的只有 3 个“aab”、“aba”、“baa”。最差的做法是生成全部排列塞进 set 里去重。能跑但浪费极大而且面试官会把分数打低。正确做法是在递归过程中剪枝在同一层递归里如果某个字符已经在当前位置尝试过了就跳过。实现方式是在 for 循环内从start到i-1扫描一遍看是否有和str[i]相同的字符for (int i start; i len; i) { int duplicate 0; for (int j start; j i; j) { if (str[j] str[i]) { duplicate 1; break; } } if (duplicate) { continue; } // 正常交换、递归、回溯 }为什么这样能去重因为在一个排列里互换两个相同的字符不会产生新的排列。当前位置start如果已经放过一个a后续再遇到另一个a产生的分支和之前完全相同。这里的j从start开始扫而不是从0开始扫也需要注意重复判断是“本轮递归中已经处理过的位置”不是全局。如果字符串可以预处理排序之后再用“相邻相同则跳过”的写法也可以但交换法里用“扫描当前区间”更通用不依赖排序也适用于数组排列。3.3 从排列延伸出去的变题这套框架能改出很多题变题改动点组合问题递归参数从start1改为i1输出不再是全排列而是前缀集合子集问题每次递归进入时都记录当前路径而不是到叶子才输出带数量限制的组合增加一个计数参数记录还能选几个组合总和进入下一层时不限定i1允许重复取同一元素字符串排列只是载体回溯框架才是真正要掌握的资产。遇到新题先判断是排列、组合还是子集再决定参数怎么传。4. 高频题解三字符统计与状态机题目4.1 第一个只出现一次的字符题目在一个字符串中找到第一个只出现一次的字符并返回它的位置。比如 “abaccdeff” 第一个只出现一次的是b。最直接的思路是两次遍历。第一次遍历统计每个字符出现次数第二次遍历按原顺序找出第一个计数为 1 的字符int firstNotRepeatingChar(const char* str) { if (str NULL) { return -1; } int counts[256] {0}; const char* p str; while (*p ! \0) { counts[(unsigned char)*p]; p; } p str; while (*p ! \0) { if (counts[(unsigned char)*p] 1) { return (int)(p - str); } p; } return -1; }这里有两个细节值得展开。第一为什么用unsigned char强转因为char在有符号平台上可能是负数比如字节0x80会被解释成 -128拿去做数组下标直接越界。强转成unsigned char能保证范围落在 0~255。第二为什么必须两次遍历不能一次遍历搞定因为“第一个只出现一次”既依赖频率信息又依赖位置顺序。如果只遍历一遍你在遇到某个字符时并不知道它在后面还会不会出现。必须先把频率表建完再回到原串按顺序找。哈希表、数组计数本质上一样区别只是字符集大小。ASCII 用int[256]最简单如果字符集是中文或 Unicode得用unordered_map。4.2 表示数值的字符串状态标志位法这题区分度很高给你一个字符串判断它是不是合法数值比如100,5e2,-1E-16算合法而12e,1a3.14,1.2.3,-5不合法。不少人一上来想写正则但正规解法更考验状态管理。我用四个标志位hasNum、hasDot、hasE、hasSign分别表示当前已扫描区域里是否已经出现过数字、小数点、指数符号、符号bool isNumber(const char* str) { if (str NULL) { return false; } const char* p str; bool hasNum false; bool hasDot false; bool hasE false; while (*p ! \0) { if (*p 0 *p 9) { hasNum true; } else if (*p .) { if (hasE || hasDot) { return false; // 小数点不能有两个指数部分不能再出现小数点 } hasDot true; } else if (*p e || *p E) { if (hasE || !hasNum) { return false; // e 前面必须有数字且只能有一个 e } hasE true; hasNum false; // e 后面也必须跟数字先重置标志 } else if (*p || *p -) { if (p ! str (p str || *(p - 1) ! e *(p - 1) ! E)) { // 符号只能在开头或指数部分的开头 return false; } p; continue; } else { return false; } p; } return hasNum; }这段代码里符号判断的写法有点绕因为要区分“字符串开头的符号”和“e后面的符号”。理解思路比背代码更重要状态机每读完一个字符更新状态如果某个状态不允许进入直接判定非法。所有非法输入都可以归结为某条规则被打破比如“指数后面不能再出现小数点”“小数点后面可以没有数字但前面必须能没有数字吗”之类的语义。我见过有人把“.5”和“3.”这类边界情况拿出来纠结不同面试题的判定标准不一样关键是在代码里体现一致的规则而不是背死答案。5. 面试官真正想考的底层存储、sizeof、const 与指针退化5.1 字符串存放区域能改和不能改的分界char s1[] hello;和char* s2 hello;这两行代码在内存层面有天壤之别。前者是在栈上分配 6 字节把字符串内容逐字节复制进去内容可修改。后者是定义一个指针变量s2它指向常量区里的字符串字面量这块区域只读尝试s2[0] H会引发未定义行为轻则崩重则静默出错。具体分区大概是栈局部变量函数调用时分配返回后失效。堆手动 malloc/new生存期由程序员控制。全局区静态变量和全局变量程序启动时分配。常量区字符串字面量等只读数据。所以面试时涉及“修改字符串”的题先确认入参是char[]还是char*。如果char*指向常量区调用方又允许你原地改那这个题本身就有坑。白板题里通常题目会说明“给定字符数组”或者“空间足够”隐含的意思就是让你原地操作不要纠结字面量只读的问题但你要能说出来为什么。5.2 sizeof 与 strlen最容易混淆的一对这两个东西几乎每场 C/C 面试都会被问而且问法花样百出。sizeof是编译期运算符计算的是类型或变量占用的字节数不关心内容。strlen是运行时函数从指针位置一直数到\0为止不含终止符。看几个例子char str[] abc; sizeof(str) // 4因为 a,b,c,\0 strlen(str) // 3 char* p str; sizeof(p) // 864位系统指针大小 strlen(p) // 3 char buf[10] {0}; sizeof(buf) // 10 strlen(buf) // 0最典型的坑是数组作为函数参数时会退化成指针。你在函数内部写sizeof(str)得到的不是数组大小而是指针大小。这就是为什么常见写法是同时传入长度或者在栈上sizeof(arr) / sizeof(arr[0])计算数组元素个数。void foo(char str[]) { // 这里的 char str[] 等价于 char* str // sizeof(str) 是 8不是数组长度 }顺带记住一个结论sizeof(abc)是 4strlen(abc)是 3。这种 1 字节的差异正是字符串存储里\0存在的意义。5.3 const 修饰指针的三兄弟老生常谈但每次问每次有人混。判断技巧就一条const离谁近谁就不能变。写法指针本身指向的内容读法const char* p可变不可变p 指向一个 const charchar* const p不可变可变p 本身是 constchar const* p可变不可变和第一种等价用代码验证const char* p1 hello; p1; // 合法指针可以移动 // p1[0] H; // 非法内容只读 char buffer[] hello; char* const p2 buffer; p2[0] H; // 合法内容可改 // p2; // 非法指针不能动这条知识在字符串题里的应用很实际如果函数只需读取字符串、不打算修改入参写const char*如果要原地修改写char*。这个签名本身就表达了你的意图面试官看一眼就能判断你的习惯。5.4 字符串作为返回值三种各自有坑第一返回局部数组的地址。这是最危险的一种char* getString() { char buf[32]; strcpy(buf, hello); return buf; // 危险函数返回后栈帧失效 }buf是栈上数组函数返回后这块内存理论上已经释放但内容大概率还在直到下一次函数调用把它覆盖。表现就是“第一次调用看起来正常第二次调用同一函数返回值变了”。正确做法有几种调用方传入缓冲区函数往缓冲区里写。函数内部 malloc调用方负责 free记得释放。用 static 局部数组但多线程环境下有共享问题别滥用。C 直接返回std::string复制语义由标准库处理最省心。第二返回字符串字面量地址。return hello;合法吗合法。它指向常量区生命周期是整个程序。但调用方如果试图修改返回值还是会崩。所以返回值类型要设计成什么取决于你是否允许调用方改内容。第三返回临时 std::string 的c_str()。C 里return std::string(abc).c_str();等于返回了一个悬空指针因为临时 string 在表达式结束时已经析构。这属于隐蔽的返回陷阱笔试选择题常考。6. 笔试现场最容易踩的五个雷从一个越界写错误开始的完整排查链路以前带过一个候选人代码提交后跑起来崩他第一反应是“数组越界”。我问怎么确认的他说看报错在 strcat 旁边。我当时就乐了报错在 strcat 旁边恰恰说明问题不一定在 strcat 里。6.1 雷一strcat 越界的完整排查链路strcat 报崩溃我通常按下面顺序查目标缓冲区容量够不够。很多人直接char dst[10] ab; strcat(dst, cdefghijklmnop);。先算一下strlen(dst) strlen(src) 1是否小于等于sizeof(dst)。目标字符串是否以\0结尾。strcat 是从dst的终止符位置开始写的。如果dst没有终止符它不知道从哪里开始写行为完全不可预知。源字符串是否有效。如果src是空指针strcat 第一步就会崩。目标地址是不是只读常量区。指向字符串字面量的char*做 strcat是典型的写只读内存崩溃报错也可能在 strcat。源字符串是否以\0结尾。如果源缓冲区里没有终止符strcat 会一直读完整个内存直到凑巧碰到一个 0 字节属于越界读。正确的替代方案是strncat或者在snprintf里控制长度但更重要的是你能说出“为什么不安全”而不是单纯换个函数。真正的排查链路是把“写之前”和“读之前”的每一个终止符和容量都验证一遍而不是盯着报错那一行看。6.2 雷二替换空格后新字符串末尾缺少终止符我见过不少人写替换空格的代码把newLength originalLength blankCount * 2算得很清楚但循环结束前忘了把\0搬过来或者只留了newLength的空间却忘记给它写终止符。后果是字符串没有结束标记后续 strlen、printf 全会越界读。从后往前复制时\0就是个普通字符和a、b一样需要移动只是它不参与空格替换。终止符只占一格永远只占一格。如果实在记不住就记住一句话复制的结果必须保证str[newLength] \0。6.3 雷三用 比较字符串内容白板题里常有人写if (s1 s2)然后面试官问他“这行代码在比较什么”他答“比较两个字符串内容”。大错特错。s1和s2如果是两个数组比较的是两个数组名各自作为指针的地址而不是内容。更坑的是两个内容相同的字符串字面量在某些编译器下会被合并到同一地址char* p1 abc; char* p2 abc;时p1 p2可能为 true 也可能为 false取决于编译器优化策略。于是你上个环境测试通过了换个编译器就过不了这是最容易踩的“隐形雷”。内容比较一律用strcmp或strncmp不要用。6.4 雷四函数返回局部数组后出现的“幽灵指针”现象很典型函数 A 返回了一个char*调用方接着用这个指针第一次打印正常再往后打印乱码。根因就是返回了栈上局部数组的地址。函数调用结束后栈帧被回收指针指向的区域可能被下一次函数调用覆盖。排查方法是看这个返回值到底指向哪里用调试器看地址如果落在当前函数的栈帧地址范围内基本可以断定是悬空指针。修复建议前面已经说了最稳的是调用方传入缓冲区。6.5 雷五忽略入参的极端状态字符串指针题还有一类不是算法难而是“空指针 空串 单字符 全相同字符 连续空格”这些边界没覆盖。我给自己定的测试清单是固定的入参是NULL函数能不能正常返回而不崩入参是空串长度为 0循环是否会进入参只有一个字符反转、替换、翻转单词是否都成立入参全部是空格翻转单词顺序后能不能正常退出最大长度如果题目说长度上限容量判断有没有写只要这五条都过一遍白板题就不容易挂。面试官不一定要求你写出健壮到能上生产环境的代码但至少要看到你脑子里有这些情况的意识。我自己的体会是字符串指针题最难的不是解法而是你永远要假设自己在“看不见内存”的条件下写代码。画内存图、标出\0、确认谁在移动、谁在写数据每一步都慢一点反而能避免大部分致命错误。准备这类题的时候我习惯把每个函数的入参约束写在注释第一行比如“要求 str 非空capacity 为数组总长度”这样无论过多久回来看都能快速进入状态。祝刷题顺利拿到心仪的 offer。
阅读完成 · 觉得有帮助？
