企业官网建设流程全解析

1. 整体设计与思路拆解：为什么是这四道题

字符串处理算是算法题里最“实在”的一类题目，因为你在日常开发里几乎天天和它打交道：用户输入校验、关键词高亮、文本编辑器的撤销操作、URL解析、日志切割，甚至数据库里的模糊查询，底层都离不开字符串的遍历、翻转和匹配。这次要聊的四个题目——反转字符串、反转字符串2、翻转字符串里的单词、重复的子字符串，恰好构成了字符串操作的一条清晰学习路径：从最基础的原地修改，到分段边界处理，再到综合性的多步操作，最后上升到模式匹配。

先说一个可能很多人忽略的事实：反转字符串这件事本身并不难，难的是“在什么约束条件下反转”。比如“反转字符串”要求原地修改、O(1)额外空间，这就排除了新建一个字符串再倒着拷贝的偷懒方案；到了“反转字符串2”，约束变成了“每2k个字符反转前k个字符”，看似只是加了规则，实际上考验的是你写循环时对区间的控制力；“翻转字符串里的单词”则把问题升级成“先清理空格、再整体翻转、最后逐个单词翻转”的多阶段流程；“重复的子字符串”更是直接跳到了KMP算法，用next数组判断一个字符串是否存在循环节。

所以这四道题不是孤立的，它们之间存在明显的递进关系。我自己的感受是，如果把这一组题连续刷完，你对“下标区间”“循环不变量”“双指针”这三件事的理解会明显上一个台阶。尤其是对准备面试的同学来说，这几道题出现的频率相当高，面试官很喜欢用它们来考察你写代码时是否考虑边界条件，以及你的代码是否简洁清晰。

这套题适合谁？一个是刚学完基础语法、准备开始刷算法的初学者，可以通过它们建立对双指针和KMP的直觉；另一个是刷题一段时间但总觉得字符串类题目不稳定的同学，这四道题能帮你把分散的知识点串联起来。本文会把每一道题的思路、为什么这么想、完整代码、复杂度分析以及我踩过的坑都拆开讲一遍，你可以直接照着写，也可以只看思路部分再自己实现。

2. 核心细节解析与实操要点

2.1 反转字符串：原地修改与双指针边界

题目要求很简单：输入一个字符数组，原地反转。不能额外申请数组，空间复杂度要求O(1)。这几乎是双指针最经典的入门场景了。

思路是左右两个指针，一个从头部往右走，一个从尾部往左走，每次交换两个位置的字符，直到两个指针相遇或者交错。这里有一个新手经常纠结的点：循环条件用left < right还是left <= right？

答案是left < right。因为在left == right的时候，两个指针指向同一个位置，交换它和自己没有任何意义，多一次无效操作而已。用left < right还有一个好处——不需要单独考虑字符数组长度为奇数还是偶数，因为中间那个字符在指针相遇时自然被跳过，不会被错误交换。

void reverseString(vector<char>& s) { int left = 0, right = s.size() - 1; while (left < right) { swap(s[left], s[right]); left++; right--; } }

复杂度是O(n)时间，O(1)空间，没有更优的解法了，因为每个字符至少要移动一次。

这里要说一个面试中的实际观察：很多候选人会直接调用库函数或者用reverse(s.begin(), s.end())，然后说“这样就行了”。这种答案不是错，但面试官大概率会追问“如果让你自己实现，你怎么做”。所以这道题真正的考察点不是你能不能反转，而是你有没有理解双指针交换的本质。建议刷题时不要图省事，手写交换逻辑，把每一步的指针变化在纸上画出来。

2.2 反转字符串2：分段处理与区间计算

“反转字符串2”的规则是：给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k个字符中的前k个字符。如果剩余字符少于k个，则将剩余字符全部反转；如果剩余字符大于等于k个且小于2k个，则反转前k个字符，其余字符保持原样。

初次看到这个规则很容易懵，记住一个判断技巧：每一段都是独立的，段的长度是2k，段内只处理前k个。我们不需要真的把字符串切成一段段再拼接，只需要让循环的步长是2k，然后对s[i, i+k)这个区间做反转。

string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n; i += 2 * k) { int left = i; int right = min(i + k - 1, n - 1); while (left < right) { swap(s[left], s[right]); left++; right--; } } return s; }

这里最关键的一行是int right = min(i + k - 1, n - 1)。它同时处理了两种边界情况：当剩余字符不足k个时，i + k - 1会越界，取n - 1正好把剩余全部反转；当剩余字符在k到2k之间时，右边界是i + k - 1，后面的字符不碰，正好符合题目要求。

这道题的核心考点是“步长”和“区间裁剪”。我见过不少实现是分段讨论、每种情况写一个if分支，结果代码又长又容易漏。用步长循环加上min裁剪区间，可以把所有情况统一成一套逻辑。写完之后建议用几个典型用例验证一下：k=1、k=3、n=4、n=5、n=6，尤其是n恰好等于2k的整数倍的情况。

2.3 翻转字符串里的单词：空格清理与多次反转的配合

“翻转字符串里的单词”是这四道题里综合性最强的。题目要求：输入一个英文句子，翻转每个单词的顺序，但单词内部字符顺序不变，同时要去掉多余的空格，比如首尾空格、单词之间的连续空格都要清理。

最经典的解法是“先整体反转，再逐个单词反转”。举个具体例子帮助理解：输入hello world，先整体反转得到dlrow olleh，你会发现整句话的顺序反了，但每个单词内部的字母也反了。这时候再对每个单词内部做一次反转，dlrow变回world，olleh变回hello，结果变成world hello，正好是目标答案。

这个思路可以用生活类比来理解：想象一叠卡片，每张卡片上写着一个单词。先整个翻过来，卡片的顺序反了；再手动把每张卡片旋转180度，卡片上的字就正了，但卡片顺序还是反的。两次反转配合，达到单词顺序翻转、单词内容不变的效果。

在实现上，比较推荐的做法是先写一个reverseRange(s, start, end)辅助函数，只反转字符串中指定区间。然后：

string reverseWords(string s) { // 1. 去除多余空格 // 2. 整体反转 // 3. 逐个单词反转 }

去除多余空格这一步看起来简单，但特别容易出问题。如果你用C++，可以用双指针原地清理：一个快指针遍历原字符串，一个慢指针记录写入位置。跳过开头的连续空格，遇到单词就写到慢指针位置，单词之间只保留一个空格。注意最后要把字符串缩到实际长度。

// 原地清理空格 int slow = 0; for (int fast = 0; fast < s.size(); fast++) { if (s[fast] != ' ') { if (slow != 0) s[slow++] = ' '; while (fast < s.size() && s[fast] != ' ') { s[slow++] = s[fast++]; } } } s.resize(slow);

这段代码里有个小细节：if (slow != 0) s[slow++] = ' ';是为了在单词之间插入空格。第一次遇到非空格字符时slow还是0，说明是第一个单词，不加空格；后续每遇到一个新单词开头，先补一个空格再写入单词内容。这个设计的精妙之处在于，它自动处理了首尾空格和连续空格，不用单独判断。

清理完空格后，整体反转，然后遍历字符串，遇到空格或走到末尾就反转当前单词区间。整个过程虽然步骤多，但每一步都很清晰。如果你用的是Python，可以直接split()再倒序拼接，代码几行就搞定。但我建议还是手动实现一遍原地版本，因为面试时手写split版本虽然简单，却体现不出你对字符串操作的控制力。

2.4 重复的子字符串：从简单思路到KMP

第四题“重复的子字符串”和前三个不太一样，它不再只依赖双指针，而是要判断一个字符串是否可以由某个子串重复多次构成。比如abab可以由ab重复两次构成，abcabcabc可以由abc重复三次构成，而aba不行。

先讲一个看起来很直观的思路：枚举可能的子串长度。如果字符串长度为n，那么子串长度len必须能被n整除，否则无法重复整数次。于是从1到n/2遍历len，对每个能整除n的len，截取前缀子串，然后重复拼接判断是否等于原字符串。这种方式的时间复杂度是O(n²)，虽然能过，但不够优雅，而且面试官大概率会追问“有没有更好的方法”。

更好的方法是KMP算法。具体做法是：求出字符串的前缀函数（next数组），记next[n-1]为整个字符串的最长相等前后缀长度。如果next[n-1] > 0且n % (n - next[n-1]) == 0，那么字符串就是由某个子串重复构成的，重复子串的长度为n - next[n-1]。

为什么这个条件成立？我一开始也被这个结论绕晕过，后来用“周期”的概念才彻底理解。最长相等前后缀的意思是：字符串的前next[n-1]个字符和后next[n-1]个字符完全相同。如果字符串存在循环节，那么n - next[n-1]正好是一个循环节的长度，总长度能被循环节长度整除，说明循环节重复了整数次。反过来，如果整段字符串的前后缀重合部分达到了n - 一个循环节长度，那字符串一定具有周期性。

举个例子验证：abab，next数组是[0, 0, 1, 2]，next[3]=2，n - next[3] = 4 - 2 = 2，4 % 2 == 0，所以存在重复子串，长度为2，即ab。再看aba，next数组是[0, 0, 1]，next[2]=1，n - next[2] = 3 - 1 = 2，3 % 2 != 0，所以不存在重复子串。

bool repeatedSubstringPattern(string s) { int n = s.size(); vector<int> next(n, 0); for (int i = 1, j = 0; i < n; i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; } if (s[i] == s[j]) { j++; } next[i] = j; } int len = n - next[n - 1]; return next[n - 1] > 0 && n % len == 0; }

这道题的难点在于KMP本身。很多人觉得KMP很难，其实只要记住next数组的本质——“当前位置之前的最长相同前缀后缀的长度”，再配合“失配时回退到next[j-1]”这一句话，就能把代码模板背下来。不要试图死记硬背，而是拿ababaca这种经典串在纸上手动推导一遍next数组的生成过程，理解之后代码自然就写出来了。

3. 实操过程与核心环节实现

3.1 环境准备与测试框架

这几道题不依赖特殊的编译环境，本地随便一个支持C++17的编译器就行。我习惯在本地写一个简单的测试函数，把关键用例一次性跑完，确认无误后再提交到在线判题系统。这样调试效率最高，还能避免反复提交浪费耐心。

一个实用的测试结构如下：

#include <iostream> #include <vector> #include <string> using namespace std; void test(string name, bool result) { cout << name << ": " << (result ? "PASS" : "FAIL") << endl; } int main() { // 反转字符串 vector<char> s1 = {'h','e','l','l','o'}; reverseString(s1); test("reverseString", s1[0]=='o' && s1[4]=='h'); // 反转字符串2 test("reverseStr", reverseStr("abcdefg", 2) == "bacdfeg"); // 翻转字符串里的单词 test("reverseWords", reverseWords(" hello world ") == "world hello"); // 重复的子字符串 test("repeatedSubstringPattern", repeatedSubstringPattern("abcabcabcabc") == true); test("repeatedSubstringPattern2", repeatedSubstringPattern("aba") == false); return 0; }

这种测试方式的优点是直观，哪个用例挂了立刻知道。我把四道题的代码放在同一个文件里，分别定义好函数，然后统一跑测试。刷题阶段保持“分而治之”的测试习惯，能帮你快速定位错误是出在算法逻辑还是边界情况。

3.2 完整代码与逐行注释

下面给出四道题的完整实现，以C++为例，每段代码都加了注释。我特意在注释里标出了容易出错的边界位置，方便直接对照。

// 题目1：反转字符串 void reverseString(vector<char>& s) { int left = 0, right = s.size() - 1; while (left < right) { swap(s[left], s[right]); left++; right--; } } // 题目2：反转字符串2 string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n; i += 2 * k) { int left = i; int right = min(i + k - 1, n - 1); // 关键：裁剪越界 while (left < right) { swap(s[left], s[right]); left++; right--; } } return s; } // 题目3：翻转字符串里的单词 string reverseWords(string s) { // 第一步：去除多余空格（首尾和连续空格） int slow = 0; for (int fast = 0; fast < s.size(); fast++) { if (s[fast] != ' ') { if (slow != 0) s[slow++] = ' '; while (fast < s.size() && s[fast] != ' ') { s[slow++] = s[fast++]; } } } s.resize(slow); // 第二步：整体反转 reverse(s.begin(), s.end()); // 第三步：逐个单词反转 int start = 0; for (int i = 0; i <= s.size(); i++) { if (i == s.size() || s[i] == ' ') { reverse(s.begin() + start, s.begin() + i); start = i + 1; } } return s; } // 题目4：重复的子字符串 bool repeatedSubstringPattern(string s) { int n = s.size(); vector<int> next(n, 0); for (int i = 1, j = 0; i < n; i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; // 失配回退 } if (s[i] == s[j]) { j++; } next[i] = j; } int cycleLen = n - next[n - 1]; // 循环节长度 return next[n - 1] > 0 && n % cycleLen == 0; }

第三题里我用了reverse库函数来简化局部反转的代码，如果你不想依赖库函数，可以仿照第一题写一个reverseRange(s, left, right)辅助函数，效果一样。重点是理解“整体反转+局部反转”的思路，而不是纠结用不用库函数。

代码写完后，我本地跑了一下测试，输出结果如下：

reverseString: PASS reverseStr: PASS reverseWords: PASS repeatedSubstringPattern: PASS repeatedSubstringPattern2: PASS

通过全部用例。这里想提醒一个细节：“翻转字符串里的单词”的第三步，循环条件是i <= s.size()而不是i < s.size()，这是为了在字符串末尾处也能触发一次单词反转。因为最后一个单词后面不一定有空格，必须让循环走到s.size()这个虚拟位置，才不会被漏掉。

3.3 复杂度对比与面试要点

四道题的时间复杂度和空间复杂度对比如下：

前三个都是原地修改，空间复杂度做到O(1)；第四题需要额外的next数组，空间复杂度O(n)。第四题其实也有另一种拼接字符串的思路：把原字符串拼接成s+s，然后去掉首尾各一个字符，如果原字符串是重复子串构成，那么s一定包含在新字符串里。这个思路实现简单，但面试时容易被追问原理，所以我还是推荐掌握KMP解法。

面试中的表达也很重要。比如第二题，不要只说“我循环步长2k”，要解释为什么步长是2k：因为题目要求每2k个字符处理一次，而且每次处理只反转前k个。还有第四题，不要只说“用KMP套模板”，要能解释next[n-1]和循环节长度的关系。能把“为什么”讲清楚，比默写代码更能加分。

4. 常见问题与排查技巧实录

4.1 双指针边界问题速查

字符串反转类题目最常见的错误就是边界判断出错。我整理了一套自查清单，几乎可以覆盖所有双指针反转场景：

• 空字符串或长度为1的字符串，直接返回，不会进入交换逻辑。
• 长度为偶数，最后一个有效交换发生在left == n/2 - 1、right == n/2时，交换后left>right，循环结束。
• 长度为奇数，中间字符不会被交换，因为此时left == right，循环条件left < right为假。
• 记住一句话：右指针永远指向有效下标，左指针不超过右指针。凡是出现越界，先检查右指针的初始化和更新逻辑。

4.2 翻转单词时的空格细节

翻转字符串里的单词，最大的坑在空格处理上。我统计自己在本地调试时遇到的几个典型问题：

第一，首尾空格没有清理干净。如果直接整体反转，首尾空格会跑到中间去，导致后续单词反转时出现多余空串。所以必须先清理空格再反转。第二，连续多个空格只保留一个。清理逻辑里if (slow != 0) s[slow++] = ' '这个设计就是为了保证每个单词前只补一个空格，但你要注意它只在单词开头触发，不会在单词内部触发。第三，C++里清理完空格后一定要resize，否则字符串尾部还会残留旧字符，输出时会看到莫名其妙的垃圾字符。

Python选手如果手写原地版本，要格外小心字符串不可变的问题。你不能像C++那样直接resize，而是要先转成list，处理完再转回字符串。这也是为什么Python解法直接用split()最省事，但原理层面还是要懂。

4.3 重复子字符串判断中的KMP误区

KMP解法里最容易混淆的是next数组的含义和最终判断条件。我拆成三点来说：

第一点：next[i]表示的是“以i结尾的子串”的最长相等前后缀长度，不是整个字符串的。因此最终判断要看next[n-1]，而不是遍历找最大值。

第二点：n - next[n-1]是循环节长度的前提是“字符串存在循环节”。如果next[n-1] == 0，说明没有相等前后缀，n - 0 = n，虽然n % n == 0，但这样会误判“整个字符串作为自己的重复子串”，这显然不对。所以判断条件必须加上next[n-1] > 0。这一点是网上很多讲解容易漏掉的地方。

第三点：理解“为什么整除条件成立”。举个例子感受一下：字符串abacaba，next数组最后一个值是3，n - 3 = 4，7 % 4 != 0，所以不是重复子串构成。而abcabc，next数组最后一个值是3，n - 3 = 3，6 % 3 == 0，存在长度为3的循环节abc。看不出来的时候，把字符串和它的next数组画出来对比，会比空想清楚很多。

4.4 避坑清单与实战心得

最后分享几条我自己刷这组题攒下来的经验，都是文档里不会写但实际很管用的东西。

不要急着调库函数。尤其是前两道反转题，用std::reverse一步到位虽然爽，但你失去了练习手写双指针的机会。面试时一旦库函数被禁用，你会突然发现自己连最基础的反转都写不利索。建议前两道题强制自己手写交换，第三题再放开用库函数。

每组边界用例都要跑一遍。我的习惯是每道题至少准备五个用例：空字符串、单字符、正好2k长度、2k-1长度、2k+1长度。这些用例跑通了，边界问题基本就不会漏。特别是第二题，n和k的各种大小关系组合起来，情况不少，但用min裁剪后一套逻辑就能全覆盖。

调试时打印中间状态。第三题特别建议在“清理空格后”、“整体反转后”、“每个单词反转后”分别打印一次当前字符串。这样一眼就能看出是哪一步把顺序搞错了。别嫌麻烦，字符串题出bug后肉眼debug效率最高。

学习和整理时把四道题放在一起。它们不是独立的个体，而是一条完整的进阶链路。先练双指针基础，再练分段边界，再练多步骤综合操作，最后练模式匹配。我个人的做法是，把这四道题的思路浓缩到一张A4纸上：左边是四段核心代码骨架，右边是边界条件和易错点。面试前只看这张纸，比重新翻题解高效很多。

后续扩展的方向。这套思路还可以延伸到不少相关题目，比如“反转链表”里的区间反转、字符串循环右移、判断旋转字符串（s+s包含s）等，核心思路都离不开“区间反转”和“周期判断”。刷完这组题后，把这些变体再扫一遍，字符串类题目的手感会稳很多。