剑指offer-题5-替换空格 解析

题目一:替换空格

请实现一个函数,把原字符串中的每个空格替换成“%20”,例如输入“We are happy”,则输出“We%20are%20happy”。

题目二:合并排序数组

有两个排序的数组A1和A2,内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数,把A2中的所有数字插入A1中,并且所有的数字是排序的。

解析

解析题目一

本题考查字符串替换,且在原字符串上改动。若考虑从头至尾遍历字符串进行字符后移,则产生多次字段移动,时间复杂度为O(n^2)。
考虑从尾至头遍历字符串进行字符后移?经书中点拨,此法甚妙😂!从尾至头仅产生一次字段移动,虽须预先测量移动距离,但仅遍历2n次,时间复杂度为O(n)。
以下为本人代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void (char *str, int length, char *aimStr, char *replaceStr)
{
if (nullptr == str || length <= 0 || nullptr == aimStr || nullptr == replaceStr)
return;
int strLength = 0;
int replaceCount = 0;
while ('