请实现一个函数，将字符串中的空格替换成“%20”

一、传统做法

从开始位置向后遍历，如果发现空格，则挪动后面的字符串腾出 2 个字符的空间，写入“%20”，直至到字符串末尾。

（灰色部分是每次要挪动的字符）

这种方法非常直观，但是性能较差。假设字符串长度为 n，其中空格数量为 m，那么时间复杂度大概为 O(m*n)，简化为 m = n，那么时间复杂度就变成了 O(n^2) 。

二、高性能做法

为了提高性能，需要尽可能的减少后面字符不必要的挪动次数，即：最后一次就能将后面的字符挪动到最终的位置上，方法就是从后面开始遍历字符串。

为了达到上述目的，需要提前知道空格替换完之后最终的字符串大小。所以开始遍历一遍字符串，假设字符串长度为 n，空格数量为 m，那么空格替换完之后的字符串长度为 len = n + m * 2 。

下一步就是开始搬运字符和替换空格的过程：

假设有两个指针分别指向了原始字符串末尾位置（p1）和最终字符串的末尾位置（p2）。首先要从后向前遍历，查看 p1 指向的字符是否是空格，如果不是的话就将该字符挪到 p2 位置上，由此类推，p1 不断向字符开始位置遍历，直至结束。

上述方法字符串每个字符挪动一次就行了，故时间复杂度为 O(n) 。

三、测试

#include 
#include void Print(const char *const p);
void ReplayBlank(char *const data, const size_t &len);
void test(const char *const data, const size_t &len);int main(int argc, char *argv[])
{test("I love China", 13);test(" I love China ", 15);test("I_love_China", 13);test("", 0);test(" ", 1);return 0;
}void test(const char *const data, const size_t &len)
{char *src = new char[len * 2]();memcpy(src, data, strlen(data));Print(src);ReplayBlank(src, strlen(src) + 1);Print(src);std::cout << "----------------------" << std::endl;delete []src;return;
}void Print(const char *const p)
{if (p == nullptr)return;std::cout << p << std::endl;return;
}void ReplayBlank(char *const data, const size_t &len)
{if (data == nullptr || len == 0)return;size_t blank_count = 0;int i = 0;while (i < len){if (data[i] == ' ')blank_count++;i++;}if (blank_count == 0)return;size_t len_all = len + blank_count * 2;char *p1 = data + len;char *p2 = data + len_all;for (i = 0; i <= len; ++i){if (*(p1 - i) != ' '){*p2 = *(p1 - i);p2--;}else{*(p2--) = '0';*(p2--) = '2';*(p2--) = '%';}}return;
}

结果：

I love China
I%20love%20China
----------------------I love China 
%20I%20love%20China%20
----------------------
I_love_China
I_love_China
--------------------------------------------%20
----------------------

注意，代码中要展现出判空、空字符串、没有空格、全是空格等情况的处理。

（SAW：Game Over！）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！