Learn-Algorithms 字符串修改专题：单词翻转、空格替换、左旋转、原地压缩与 strcpy 实战解析

教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载本篇技术指南以仓库内 1.3 字符串-修改.md 为骨架系统讲解算法面试中最常出现的一类字符串操作题翻转句子中单词的顺序、将空格替换为%20、左旋转字符串、字符串原地压缩以及手写strcpy。这些题目共同考察三个底层能力——双指针扫描、从后向前原地搬运、两次逆序的化归思维并普遍要求在 O(n) 时间内完成、尽量不占用额外空间。读完本文你将掌握每道题的可运行 C 实现、边界条件与复杂度分析并能对照仓库codes/1 string/下的真实源码加深理解。1. 专题总览字符串修改类题目考什么字符串修改与字符串查找、字符串删除共同构成字符串面试题的三大分支。本专题的五道题有一个共同点必须直接在原串上或利用既有缓冲区完成修改由此带来两类核心约束空间约束不允许或尽量少地开辟临时数组需要在原地完成数据搬移长度变化约束替换、压缩会导致字符串变长或变短搬移方向从前往后/从后往前的选择直接影响正确性。题目核心手法时间复杂度额外空间翻转句子中单词的顺序整体逆序 按单词逆序两次逆序O(n)O(1)替换空格为 %20统计空格 从后往前搬运O(n)O(1)前提缓冲区足够大左旋转字符串分段逆序 整体逆序O(n)O(1)字符串原地压缩双指针扫描 计数O(n)O(1)输出到 dest 时除外手写 strcpy边拷贝边检测终止符O(n)O(1)下面逐题展开。2. 翻转句子中单词的顺序2.1 题目与函数原型输入一个英文句子翻转句子中单词的顺序但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见标点符号和普通字母一样处理。 例如输入I am a student.则输出student. a am I。char *revert_by_word(char *source);2.2 核心思路两次逆序原文档给出了两种等价的做法原地整体逆序字符串两端的字符逐个交换然后再按单词逆序先按单词逆序再对整个句子逆序。两条路线本质相同都是把单词顺序反转 单词内部顺序保持这个大问题拆解成两次纯粹的区间逆序操作。以I am a student.为例路线一原始串: I am a student. 整体逆序: .tneduts a ma I 按单词逆序: student. a am I ✓2.3 无临时空间的字符交换技巧原文档特别强调在不允许临时空间即字符交换不能借助临时变量的情况下可以像交换两个整数一样完成字符交换加减法交换注意 char 的字节宽度长字符串叠加可能溢出需按题目限定取舍char a a, b b; a a b; b a - b; a a - b;异或交换不产生进位无溢出风险可安全用于字符交换a a ^ b; b a ^ b; a a ^ b;仓库 string.c 中的revertByWord正是采用加减法完成交换且选择了先按单词逆序、再整体逆序的路线二两份实现互为印证。2.4 参考实现与源码对照原文档给出的完整实现这里修正了原稿中start,处误写的逗号运算符#include stdio.h /* 将 [start, end] 区间的字符逆序 */ void _reverse(char *start, char *end){ if ((start NULL) || (end NULL)) return; while (start end){ char tmp *start; *start *end; *end tmp; start; end--; } } /* 只做按单词逆序句子整体顺序不变每个单词内部逆序 */ char *_revert_by_word(char *source){ char *start source; char *end source; while (*start ! \0){ if (*start ){ /* start 指向空格两指针同时前进 */ start; end; } else if (*end || *end \0){ /* end 抵达单词右边界 */ _reverse(start, end - 1); /* 逆序当前单词 */ start end; } else { end; /* end 仍在单词内部继续前进 */ } } return source; } /* 翻转句子中单词的顺序先整体逆序再按单词逆序 */ char *revert_by_word(char *source){ char *start source; char *end source; if (source NULL) return NULL; while (*end ! \0) end; /* end 先移动到字符串末尾 */ end--; /* 回退到最后一个字符 */ _reverse(start, end); /* 第一步整个句子逆序 */ _revert_by_word(source); /* 第二步每个单词内部逆序 */ return source; }仓库中的 revert_by_word.c 与文档代码几乎逐行一致它将上面两个阶段拆成了_revert_by_word仅按单词逆序与revert_by_word整体逆序 调用前者说明作者维护的即整体逆序 → 按单词逆序这一路线。原文档与源码中start,的逗号书写属于笔误逗号运算符使该表达式退化为仅start生效编译和逻辑上不影响正确性但面试手写时应使用分号。从源码还可以得到一个重要的实战教训revert_by_word.c的main中char *test how are you ?; printf(%s\n, _revert_by_word(test)); // 运行时 bus error把字符串字面量直接传给原地修改函数会触发 bus error——因为字符串字面量位于只读存储区原地修改会写入非法内存。正确做法是像 replce_blank.c 那样声明可写的字符数组char str[100] we are happy;这也是面试中常见的隐蔽扣分点原地修改类题目测试用例必须用char[]而非char *指向的常量串。2.5 变体字符串整体逆序原文档随后列出两条同类变体不开辟用于交换数据的临时空间如何完成字符串的逆序用 C 语言实现一个revert函数功能是将输入字符串在原串上倒序后返回。这两题就是_reverse本身只需一趟首尾交换。仓库 string.c 中的revert(source, dest)给出了先拷贝到目标缓冲区再首尾交换的版本可作参考。3. 替换空格为 %203.1 问题本质与前置条件实现一个函数把每个空格替换成%20。如输入we are happy则输出we%20are%20happy。char *replce_blank(char *source);这道题的难点在于一个字符被替换成三个字符替换后的字符串比原串更长。若要在原串上直接修改不能顺序从前向后替换否则替换出的%20会覆盖尚未处理的字符原串的空间必须足够大能容纳替换变长后的结果如果空间不够就只能新建一块缓冲区保存结果原文档明确这里假设空间足够。顺带一提原文档标题与函数名存在拼写不一致标题与声明写作replce_blank下方完整代码使用的是replace_blank阅读源码、grep 时注意两种写法并存仓库文件名同样为replce_blank.c函数名为replace_blank。3.2 两步法实现原文档给出的算法分两步第一遍扫描统计空格个数n替换后的字符串长度 原长度 2n从后向前扫描逐个挪动字符位置碰到空格时改写为%20由于从后往前写%20不会覆盖未处理的字符。完整实现含可运行测试#include stdio.h char *replace_blank(char *source){ int count 0; char *tail source; if (source NULL) return NULL; /* 第一遍统计空格个数tail 最终停在 \0 上 */ while (*tail ! \0){ if (*tail ) count; tail; } /* 第二遍从后向前搬运tail 每处理一个空格就少一个待替换的空格 */ while (count){ if (*tail ! ){ /* 普通字符后移 2*count 个位置 */ *(tail 2 * count) *tail; } else { /* 空格从后往前依次写 0、2、% */ *(tail 2 * count) 0; *(tail 2 * count - 1) 2; *(tail 2 * count - 2) %; count--; } tail--; } return source; } int main(void){ char str[100] we are happy; /* 必须用可写字符数组 */ printf(ret%s\n, replace_blank(str)); /* we%20are%20happy */ return 0; }逐字节验证we are happy2 个空格最终长度 13 4 17tail最初指向\0先把终止符搬到新串尾索引 16随后y、p、p、a、h依次后移 4 位遇到第一个空格时在其目标位置当前索引 2×剩余空格数写入0、2、%处理完剩余字符与第二个空格后恰好得到we%20are%20happy。核心不变量是2*count恰好等于当前字符之后的空格所贡献的额外长度因此每个字符都能精确落到最终位置。3.3 源码对照与验证仓库 replce_blank.c 中的replace_blank与文档实现完全一致其main同样声明char str[100]we are happy并用%s打印验证结果可以直接编译运行复现输出。3.4 复杂度与边界讨论时间复杂度 O(n)两趟线性扫描空间复杂度 O(1)不新建字符数组但依赖调用方预先准备足够大的缓冲区边界空串第一遍循环不执行直接返回原串、无空格count为 0第二遍循环不执行、source NULL函数首行防御性返回。4. 左旋转字符串4.1 题目要求字符串的左旋转操作把字符串前面的若干个字符移动到字符串的尾部。 如把字符串abcdef左旋转 2 位得到cdefab。要求时间对长度为 n 的字符串操作的复杂度为O(n)辅助内存为O(1)。char *left_rotate(char *str, int offset);4.2 思路分段逆序再整体逆序原文档点明我们可以把abcdef分成两部分ab和cdef内部逆序以后整体再次逆序就可以得到想要的结果了……跟上面的问题是同样的问题。这与第 2 节两次逆序是同一套路只是逆序的对象从整个句子 每个单词换成了两个子段 整个字符串原始: abcdef 前段逆序: bacdef (ab - ba) 后段逆序: bafedc (cdef - fedc) 整体逆序: cdefab ✓4.3 参考实现与边界处理原文档只给出函数骨架此处依据其分段逆序 整体逆序思路给出完整参考实现属于对题目思路的补全非仓库既有代码void _reverse(char *start, char *end){ while (start end){ char tmp *start; *start *end; *end tmp; start; end--; } } char *left_rotate(char *str, int offset){ if (str NULL) return NULL; int len 0; char *p str; while (*p ! \0){ len; p; } if (len 1) return str; offset offset % len; /* offset 可能大于 n先取模 */ if (offset 0) return str; /* 左旋 0 位或负数无需处理 */ _reverse(str, str offset - 1); /* 前段内部逆序ab - ba */ _reverse(str offset, str len - 1); /* 后段内部逆序cdef - fedc */ _reverse(str, str len - 1); /* 整体逆序bafedc - cdefab */ return str; }三次逆序各为 O(n/2) 量级的交换总计 O(n)且全程原地、辅助空间 O(1)满足题目约束。边界上需要处理空串与单字符、offset大于字符串长度先取模、offset为 0 或负数直接返回。5. 字符串原地压缩5.1 题目与注意事项将abeeeeegaaaffa压缩为abe5ag3f2a请编程实现。char *compress(const char *src, char *dest);原文档明确列出这道题的三处坑单个字符不压缩——a单独出现时保持a不写作a1压缩后字符个数可能是多位数超过 10 个连续相同字符如 15 个a要写作a15不能是a1 5之类原地压缩最麻烦的地方是数据移动——压缩会改变字符串长度搬移方向与指针协作稍有不慎就会覆盖数据。5.2 双指针思路原文档描述了双指针方案使用两个指针一前一后扫描——两指针指向的字符不相等时两指针都前进一位相等时后一位改为数字 2且后面的指针再前移一位仍然相等则数字加 1直到不相等为止。这本质上是快慢指针 连续段计数快指针负责探路找出每个连续相同字符段的右边界慢指针负责写出字符与次数。5.3 参考实现含多位数处理原文档仅给出函数骨架这里按上述双指针思路补全一个可直接运行的参考实现重点演示多位数次数的处理char *compress(const char *src, char *dest){ if (src NULL) return NULL; char *d dest; const char *p src; while (*p ! \0){ /* 统计当前字符连续出现的次数 */ const char *q p; int count 0; while (*q *p){ count; q; } *d *p; /* 先写出字符本身 */ if (count 1){ /* 单个字符不压缩 */ if (count 10){ *d 0 count; /* 一位数直接写 */ } else { /* 多位数逐位写入临时缓冲区再反转写出保证高位在前 */ char buf[16]; int k 0; while (count 0){ buf[k] 0 count % 10; count / 10; } while (k 0) *d buf[--k]; } } p q; /* 跳到下一个不同的字符 */ } *d \0; return dest; }验证abeeeeegaaaffa依次处理a(1)→a、b(1)→ab、e(5)→abe5、g(1)→abe5g、a(3)→abe5ga3、f(2)→abe5ga3f2、a(1)→abe5ga3f2a输出正确。若把输入换成 15 个连续a则输出a15体现多位数分支的作用。仓库 string.c 中保留了该题的compress函数骨架与注释注意连续字符大于9的情况方向一致但实现未完成阅读源码时可对照本文的完整版本理解作者意图。另注意原文档给出的签名是compress(const char *src, char *dest)即输出到独立 dest 缓冲区若题目要求真正的原地压缩还需像字符串删除中的双指针删除那样让慢指针直接覆盖快指针扫过的位置并最后补\0——这正是数据移动最麻烦的原因。5.4 压缩率与输入特征的关系原文档特别指出压缩算法的效率验证依赖给定字符串的特性。对aaaaaaaa...aaa这类大量重复的输入上述算法压缩率接近 100%反之对几乎无重复字符的输入压缩率可能趋近 0%输出长度与原串相当甚至需要额外写入字符。因此面试中评估压缩效果时不能只看算法本身还要说明其针对的输入分布——这也提示我们测试时要覆盖全重复、全不同、单字符、多位数次数四类用例。6. 编写 strcpy 函数6.1 题目要求已知strcpy的原型char *strcpy(char *strDest, const char *strSrc);其中strDest是目的字符串strSrc是源字符串要求不调用 C/C 的字符串库函数。6.2 参考实现与源码对照原文档仅给出原型下面给出满足题目要求的完整实现char *strcpy(char *strDest, const char *strSrc){ if (strDest NULL || strSrc NULL) return NULL; /* 防御性检查 */ char *d strDest; while ((*d *strSrc) ! \0); /* 边拷贝边检测终止符 */ return strDest; /* 返回目标指针 */ }关键设计点返回strDest而非void返回目标指针是原型要求也是面试考点之一便于链式调用用赋值表达式同时完成拷贝与终止判定(*d *strSrc) ! \0先拷贝再判断恰好把源串的\0也一并拷贝过去无需额外补终止符参数用const char *修饰源串表明只读源防止误写。仓库 string.c 中保留了一份等价的strcpy实现先拷贝到dest、补\0再返回目标指针tmp可以作为对照阅读。6.3 常见考点与易错点是否处理了空指针NULL返回值是否为strDest源串的\0是否被正确拷贝漏拷会破坏目标串的终止目标缓冲区大小与源串长度的关系strcpy不检查越界这是面试官常用来引申讨论strncpy/memcpy的入口。7. 总结字符串修改的通用方法论纵观本专题五道题可以提炼出三套反复出现的通用方法论两次逆序的化归思维翻转单词顺序 整体逆序 按单词逆序左旋转 分段逆序 整体逆序。凡是局部保持顺序、整体改变顺序的题目都可以尝试用逆序操作化归从后向前搬移凡是替换后字符串变长如空格 →%20的原地修改一律从后向前搬运避免覆盖未处理数据反之删除/压缩这类变短操作则适合从前往后的双指针覆盖参见1.2 字符串-删除.md双指针协作快指针探路、慢指针落位几乎贯穿所有原地字符串题包括压缩、删除、过滤等变体。复杂度上本专题所有题目的最优解均为O(n) 时间、O(1) 辅助空间这也是面试官对原地修改类题目的默认期待。建议在掌握本文代码后把每道题的输入输出 边界用例空串、单字符、多空格、多位数次数、字符串字面量陷阱整理成测试集按 codes/1 string 目录中既有示例的方式编译验证。延伸阅读本专题属于 1 字符串.md 中字符串常见问题的修改分支与之配套的还有 1.1 字符串-查找.md子串查找/KMP、1.2 字符串-删除.md双指针删除与 1.4 字符串-排序.md建议串联阅读形成查找—删除—修改—排序的完整字符串知识闭环。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Mistral-7B中文对话模型实战部署完整方案从零到生产级深度优化Mistral 7B中文对话模型实战部署完整方案从零到生产级深度优化 面对当前AI应用部署中普遍存在的GPU资源紧张、推理速度慢、部署复杂度高等挑战MistLearn-Algorithms项目中的字符串处理替换与反转操作Learn Algorithms项目中的字符串处理替换与反转操作 在日常编程中字符串处理是最常见的任务之一。无论是用户输入验证、数据清洗还是文本分析都离不教程CS-Notes 剑指 Offer 58.2 左旋转字符串三次翻转完成字符串左移的 O(n) 解法CS Notes 剑指 Offer 58.2 左旋转字符串三次翻转完成字符串左移的 O n 解法 本篇基于 notes/58.2 左旋转字符串.md http知识库文档教程上一篇TV Bro vs 传统浏览器智能电视场景下的用户体验深度对比下一篇Roc 语言开放标签联合Open Tag Union的格式化稳定性从快照测试看 .. 扩展标记的空白处理规则创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考