精品题解 ? 《九章斩题录》  ? 猛戳订阅

? 目录：

JZ5 - 替换空格

「 法一 」暴力美学

「 法二 」另开数组

「 法三 」反向替换（利用 rfind + replace）

「 整活 」不用C++，Python 一行代码搞定

JZ5 - 替换空格

? 题目：请实现一个函数，将一个字符串  中的每个空格替换成 " %20 " 。例如当字符串为 We Are Happy.  则经过替换之后的字符串为 We%20Are%20Happy 。

? 示例：I/O

输入："We Are Happy"
返回："We%20Are%20Happy"

输入：" "
返回："%20"

✅ 模板：C语言

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串
 */
char* replaceSpace(char* s ) {
    // write code here
}

✅ 模板：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
    }
};

「 法一 」暴力美学

? 思路：两次循环遍历整个数组，第一次循环寻找空格的位置，第二次循环将空格后的字符整体后移 2 个单位 (腾出空间给 %20)，然后再将 %20 插入即可。因为 ''%20'' 为 3 个字符，分别是 (%, 2, 0)，因为空格处用来放置 '%'，所以只需腾出 2 个空间给 '2' 和 '0' 即可。

 循环次数为两次，因此时间复杂度为 ，空间复杂度为 。

? 代码演示：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // 统计空格数
        int i = 0;
        int count = 0;
        for (i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 重新开大小，大小为 旧字符串大小 + 空格数 x 2
        // 这样就有足够的位置放 %20了
        // 原字符串空格放%，新开的放 2 和 0
        s.resize(s.size() + count * 2);

        i = 0;
        int j = 0;
        while (i < s.size()) {
            if (s[i] == ' ') {
                // 整体后移两个单位
                for (j = s.size() - 1; j > i + 2; j--) {
                    s[j] = s[j - 2];
                }
                s[i] = '%';
                s[i + 1] = '2';
                s[i + 2] = '0';
            }
            else {
                i++;
            }
        }

        return s;   // 返回原字符串
    }
};

「 法二 」另开数组

? 思路：我们直接重新开一个字符数组，依次读取原整个字符串的内容，读到空格就在后面加上 '‘%20'' 然后继续读。其主要思路如下：

① 创建一个新的字符型数组，用于存放替换空格后的字符串。
② 从头到尾遍历字符串 ，遍历到  为止。
③ 对每个字符都进行判断，判断当前字符是否为空格，如果为空格就分别向后插入 %, 2, 0。
④ 如果当前字符不是空格，就将当前字符串的字符直接加到新数组中。
⑤ 最后记得在新数组末尾手动加上 ，最后返回新数组即可，此时就实现了空格的替换。

这种方法需要创建新的空间，不修改源字符串，这种方法非常易于理解和实现，属于 "重新来过" 的思想。其时间复杂度为 ，空间复杂度为 。

? 代码演示：C

char* replaceSpace(char* s ) {
    char arr[10000] = {0};
    int i = 0;

    while (*s != '') {
        if (*s == ' ') {
            arr[i++] = '%';
            arr[i++] = '2';
            arr[i++] = '0';
        }
        else {
            arr[i++] += *s; 
        }
        s++;
    }
    arr[i] = '';

    return arr;
}

「 法三 」反向搜空格然后替换（利用 rfind + replace）

? 思路：有现成的 replace 接口可以拿来替换，又有现成的 find 接口可以拿来查找空格。直接调接口来解决问题，岂不美哉？这里我们用 rfind 反向查找，从字符串  的末尾向前查找空格，如果找到就调用 replace 把空格替换成 '%20' 即可。

? 代码：C++

class Solution {
public:
    string replaceSpace(string s) {
        int end = s.size() - 1;    // 字符串s的最后一个元素的下标

        while (string::npos != s.rfind(' ', end)) {
            int space = s.rfind(' ', end);    // 倒着找空格，避免覆盖
            s.replace(space, 1, "%20");       // 将字符串s中空格开始的1个字符替换为%20
            end = space;                      // 下次从空格前一个位置开始查找
        }

        return s;
    }
};

先定义 end 用于记录最后一个字符的位置，然后倒着遍历字符串。这里的循环条件是判断 rfind 是否为 npos，因为当 find 或 rfind 在字符串中找不到指定字符或子字符串时，它们会返回 string::npos。如果是 npos 那就说明没找到空格，说明查找完毕了，就结束循环。如果有空格，我们就记录空格的位置，然后调用 replace，把空格替换成 %20，然后更新我们的 end。每次循环都会判断是否存在空格，如果从右向左找一遍没有空格也就没有必要在进入循环，说明没有需要替换的，或者已经替换完了，这时直接 return s 即可。

⚡ 代码简化：

class Solution {
public:
    string replaceSpace(string s) {
        int space, end = s.size() - 1;
        for (; (space = s.rfind(' ', end)) != string::npos; end = space)
            s.replace(space, 1, "%20");
        return s;
    }
};

「 整活 」不用C++了，Python 一行代码搞定

"人生苦短，我用 Python…… "

不用做了，用隔壁蟒蛇直接一行结束了。

return s.replace(' ', "%20")

​

? [ 笔者 ]   王亦优
? [ 更新 ]   2023.5.30
❌ [ 勘误 ]   /* 暂无 */
? [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！