替换空格（C++和Python 实现）

（说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”）

题目

    请实现一个函数，把字符串中的每个空格替换为 "%20" 。例如输入 "We are happy.", 则输出 "We%20are%20happy." 。

    进一步详细说明：

    在网络编程中，如果 URL 参数中含有特殊字符，如空格、'#'、':' 等，可能导致服务器端无法获得正确的参数值。我们需要这些特殊符号转换成服务器可以识别的字符。转换规则是在 '%' 后面跟上 ASCII 码的两位十六进制的表示。如空格的 ASCII 码是 32，即十六进制的 0x20，因此空格被替换成 "%20" 。再比如 '#' 的 ASCII 码为 35，即十六进制的 0x23，它在 URL 中被替换为 "%32"。再比如 ':' 的 ASCII 码为 50，即十六进制的 0x32，它在 URL 中被替换为 "%32"。

算法设计思想

1. 时间复杂度为 O(n²) 的算法思想

    从头到尾，扫描字符串中的每个字符，遇到空格，先将剩余的字符（未遍历到的字符串）整体向后移动2个位置，然后，在空格和其后的2个字符的替换为"%20"。

2. 时间复杂度为 O(n) 的算法思想

    先遍历整个字符串，计算字符串中空格的总数，从而可以计算出替换后的字符串长度（根据替换规则，每次替换空格时，都会使字符串的长度增加2）。然后，使用两个指针或索引，从后往前遍历，即初始化指针或索引分别指向替换前和替换后字符串的末尾，循环递减，如遇到空格，则替换为 "%20"，从而减少字符串移动的次数，降低时间复杂度。

C++ 实现

#include <iostream>

// Replace blank " " with "%20"
// Note - the 'length' parameter is the maximum length of the array
void ReplaceBlanks(char str[], int length)
{
    if (str == NULL || length <= 0)  // 易漏点
        return;

    // Count the number of blanks
    char *pChar = str;
    int strLen = 0;
    int blanksCount = 0;
    while (*pChar++ != '