剑指offer第2版——面试题5：替换空格
一、题目
请实现一个函数，把字符串s中的每个空格替换成 “%20”。
示例：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：0 <= s的长度 <= 10000
二、答案
2.1 我的答案
暴力求解法，时间复杂度较高！
#include <string>
#include <iostream>
using namespace std;
/*把空格替换成%20*/
void repalceBlock(char* aim, int len)
{if (nullptr == aim|| len<=0){return;// 立即结束函数，不再执行后面的代码}/*计算出有多少个空格*/int numberOfBlock = 0;int originLen = 0;int i = 0;while (aim[i] != '\0'){originLen++;if (' ' == aim[i]){numberOfBlock++;}i++;}cout << "空格数量是：" << numberOfBlock <<endl;int newLength = originLen + numberOfBlock * 2;if (newLength > len) {return; // 缓冲区不足，无法完成替换}int p1 = originLen;int p2 = newLength;while (p1>=0 && p2>p1){if (aim[p1] == ' '){aim[p2--] = '0';aim[p2--] = '2';aim[p2--] = '%';}else{aim[p2--] = aim[p1];}p1--;}}int main() {char aim[20] = "We are happy";repalceBlock(aim,sizeof(aim));cout << aim;return 0;
}
2.2 标准答案
#include <string>
#include <iostream>
using namespace std;
/*把空格替换成%20*/
string replaceSpaces(string& str) {int len = str.length();int space = 0;// 统计空格数量for (char c : str) {if (c == ' ') {space++;}}// 修改字符串长度str.resize(len + 2 * space);int p1 = len - 1;int p2 = str.length() - 1;while (p1 >= 0) {if (str[p1] == ' ') {str[p2--] = '0';str[p2--] = '2';str[p2--] = '%';}else {str[p2--] = str[p1];}p1--;}return str;
}int main() {string aim = "We are happy";replaceSpaces(aim);cout << aim;return 0;
}2.3 解析
参考剑指向offer
三、考察点
这个问题看似简单，实则考察以下编程基础：
- 字符串操作能力：如何高效遍历字符串、处理字符替换（尤其需要考虑原字符串长度变化对内存的影响）。
- 边界情况处理：空字符串、连续空格（如
"a b"）、字符串首尾空格等场景的正确处理。 - 时间与空间效率意识：例如在 C++ 中，若先计算空格数量再扩容字符串，可以避免频繁的内存重新分配，提升效率。
总之，个问题的本质是对网络通信中字符编码规则的实际应用，同时考察基础的字符串处理逻辑。
四、背景知识
在字符串中替换空格为%20的需求，本质上与URL 编码规则密切相关，是网络通信和数据传输中非常基础且重要的处理逻辑。以下从具体场景和技术原理两方面详细讲解：
核心需求来源：URL 的特殊字符编码规则
在网络传输中，URL（统一资源定位符）是标识资源位置的字符串，例如https://www.example.com/search?query=hello world。但 URL 中不允许直接包含空格等特殊字符，原因是：
- 早期的网络协议（如 HTTP）规定，URL 只能由字母、数字和部分符号（如
-、_、.等） 组成，空格不在允许范围内。 - 若直接包含空格，会导致 URL 解析错误（例如服务器无法区分空格是参数的一部分，还是分隔符）。
因此，需要一种编码方式将空格等特殊字符转换为 URL 允许的格式，%20就是空格的URL 编码结果（其中20是空格字符在 ASCII 表中的十六进制值，%是编码标识）。
实际应用场景：
- 网页表单提交
当用户在搜索框、输入框中输入包含空格的内容（如 “hello world”），浏览器会自动将空格替换为%20后再发送请求。例如：
输入内容"We are happy"，提交后实际发送的 URL 参数会变为We%20are%20happy。 - URL 参数拼接
在后端开发中，若需要动态生成包含空格的 URL（如根据用户输入拼接参数），必须手动替换空格为%20，否则会导致链接失效。例如：
拼接用户昵称"John Doe"作为参数时，需转换为"John%20Doe"才能正确被服务器解析。 - 文件路径处理
部分系统或协议中，文件路径中的空格也需要编码为%20（尤其是跨平台传输时），避免因操作系统对空格的处理差异导致错误。1
五、扩展知识
5.1 知识1：字符数组如何作为函数参数传递？
char aim[] = "We are happy";
5.1.1 传递数组名（隐式转换为指针）
字符数组名在作为参数时会隐式转换为指向首元素的指针（char* 或 const char*），这是最常用的方式。
（1）传递可修改的字符数组（char* 参数）
如果需要在函数中修改数组内容，参数用 char*：
#include <iostream>// 传递char*，可修改数组内容
void modifyArray(char* arr) {if (arr != nullptr) {// 例如：将第一个字符改为大写if (arr[0] >= 'a' && arr[0] <= 'z') {arr[0] -= 32;}}
}int main() {char str[] = "hello"; // 字符数组modifyArray(str); // 传递数组名（隐式转为char*）std::cout << str << std::endl; // 输出 "Hello"return 0;
}
（2）传递只读的字符数组（const char* 参数）
如果只需读取数组内容，参数用 const char*（更安全，且兼容字符串字面量）：
#include <iostream>
#include <cstring>// 传递const char*，仅读取数组内容
int getArrayLength(const char* arr) {if (arr == nullptr) return 0;return std::strlen(arr); // 依赖'\0'计算长度
}int main() {char str[] = "world";std::cout << "长度：" << getArrayLength(str) << std::endl; // 输出 5return 0;
}
5.1.2 传递数组时指定长度（避免依赖 \0）
如果字符数组中可能包含 \0（非字符串），或需要精确控制处理范围，需额外传递数组长度：
#include <iostream>// 传递数组指针 + 长度（处理任意字符数组，不依赖'\0'）
void printArray(const char* arr, int length) {for (int i = 0; i < length; ++i) {std::cout << arr[i];}std::cout << std::endl;
}int main() {char arr[] = {'h', 'i', '\0', '!', '!'}; // 包含'\0'的字符数组int len = sizeof(arr) / sizeof(arr[0]); // 计算数组总长度（5）printArray(arr, len); // 输出 "hi!!"（包含'\0'但仍打印所有元素）return 0;
}
5.1.3 传递数组引用（指定大小，较少用）
可以传递数组的引用，但必须显式指定数组大小（灵活性低，仅适用于固定大小的数组）：
#include <iostream>// 传递数组引用（必须指定大小，如[6]）
void funcWithArrayRef(char (&arr)[6]) { // 仅接收大小为6的char数组arr[0] = 'H';
}int main() {char str[] = "hello"; // 大小为6（5个字符 + '\0'）funcWithArrayRef(str); // 正确：数组大小匹配std::cout << str << std::endl; // 输出 "Hello"return 0;
}
关键总结
| 传递方式 | 语法示例 | 适用场景 | 注意事项 |
|---|---|---|---|
| 指针（可修改） | void func(char* arr) | 需要修改数组内容，处理字符串（依赖 ‘\0’） | 需检查空指针，避免越界 |
| 指针（只读） | void func(const char* arr) | 仅读取内容，兼容字符串字面量 | 不可修改内容，需检查空指针 |
| 指针 + 长度 | void func(const char* arr, int len) | 处理含 ‘\0’ 的数组，精确控制范围 | 需手动传递长度，确保不越界 |
| 数组引用（固定大小） | void func(char (&arr)[N]) | 严格限制数组大小，需精确匹配 | 灵活性低，仅适用于固定大小数组 |
实际开发中，const char\*（只读） 和 char\*（可修改） 是最常用的方式，配合字符串结束符 \0 处理常规字符串。如果是二进制数据或含 \0 的字符数组，务必额外传递长度参数。
5.2 知识2：“ ”和‘ ’有啥区别？
在 C/C++ 中，' ' == *aim 和 " " == *aim 有本质区别，前者是正确的，后者会导致编译错误或逻辑错误，具体区别如下：
5.2.1 ' '（单引号）：表示单个字符
' '是字符常量，代表一个空格字符，类型为char，在内存中占用 1 字节。*aim是指针aim指向的字符（char类型），因此' ' == *aim是正确的字符比较，用于判断当前字符是否为空格。
你的代码中 ' ' == *aim 是正确的写法，用于统计空格数量：
if (' ' == *aim) // 正确：判断当前字符是否为空格
{numberOfBlock++;
}
5.2.2 " "（双引号）：表示字符串字面量
" "是字符串常量，代表一个包含空格字符和终止符\0的字符串（即{' ', '\0'}），类型为const char[2]（长度为 2 的字符数组）。- 当使用
" "时，它会隐式转换为const char*指针（指向字符串首地址）。
此时 "" == *aim 会变成 const char* 与 char 的比较，两者类型完全不匹配：
if (" " == *aim) // 错误：类型不匹配（const char* vs char）
- 编译器会直接报错（类型不兼容），因为无法比较一个指针和一个字符。
- 即使某些编译器允许（实际不会），比较的也是指针地址和字符的 ASCII 码值，逻辑上毫无意义。
5.2.3 总结
' '是单个字符，用于与char类型的变量（如*aim）比较，判断是否为空格，你的代码中这部分是正确的。" "是字符串，无法与单个字符比较，会导致编译错误，绝对不能这样写。
在 C/C++ 中，单引号用于单个字符，双引号用于字符串，这是基础语法规则，必须严格区分。
5.3 指针访问方式：aim[i]等价于*(aim+i)
在 C/C++ 中，指针完全支持 aim[i] 这种访问方式，它与 *(aim + i) 是完全等价(效率完全等价)的，是指针访问元素的两种等效写法。
对于指针 char* aim：
aim[i]本质上是*(aim + i)的语法糖，编译器会自动将其转换为指针偏移后取值的形式。- 例如：
aim[0]等价于*aim（指针指向的第一个元素）。aim[1]等价于*(aim + 1)（指针偏移 1 字节后指向的元素）。- 以此类推，
aim[i]就是指针向后偏移i个元素后指向的内容。
5.4 为什么 originalLength 不一定等于 len - 1？
- 情况 1：缓冲区未被填满
若原始字符串实际长度较短（比如字符串是"a b"，实际长度为 3，包含 1 个空格），而缓冲区容量len较大（比如len = 10），则originalLength = 3，而len - 1 = 9，显然不相等。 - 情况 2：缓冲区刚好填满
若原始字符串刚好占满整个缓冲区（比如字符串长度为 9，len = 10），则originalLength = 9，len - 1 = 9，此时二者相等。 - 情况 3：字符串超长（不合理但可能存在）
若原始字符串没有正确的'\0'结束符（比如错误输入），则遍历会一直进行，可能导致originalLength超过len - 1，但这种情况属于非法输入（函数会通过后续的newLength检查避免越界）。
总结:
originalLength 是 字符串实际有效字符的总数（含空格，不含 '\0'），而 len - 1 是 缓冲区理论上能容纳的最大有效字符数。二者是否相等，取决于字符串是否填满了整个缓冲区。
在正常情况下（字符串有正确的 '\0' 且未超出缓冲区），originalLength 一定 小于或等于 len - 1，但不一定等于 len - 1。