剑指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
28void replace(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 ('\0' != str[strLength++])
if (0 == strncmp(&str[index], aimStr, strlen(aimStr)))
++replaceCount;
int strNewLength = strLength + replaceCount * (strlen(replaceStr) - strlen(aimStr));
if (strNewLength > length)
return;
int index = strLength;
int indexNew = strNewLength;
while (index >= 0 && indexNew > index)
{
if (0 == strncmp(&str[index], aimStr, strlen(aimStr)))
{
indexNew -= strlen(replaceStr) - strlen(aimStr);
// strcpy将自动在尾部附加结束符\0，故采用memcpy
memcpy(&str[indexNew], replaceStr, strlen(replaceStr));
}
else
str[indexNew] = str[index];
--index;
--indexNew;
}
}
解析题目二
思路与上题相同，附上本人代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void combine(int *aimArr, int aimArrLength, int length, int *insertArr, int insertArrLength)
{
if (nullptr == aimArr || aimArrLength <= 0 || length <= 0 || nullptr == insertArr || insertArrLength <= 0)
return;
int newLength = aimArrLength + insertArrLength;
if (newLength > length)
return;
int indexAim = aimArrLength - 1;
int indexInsert = insertArrLength - 1;
int indexNew = newLength - 1;
while (indexNew >= 0)
if (aimArr[indexAim] > insertArr[indexInsert])
aimArr[indexNew--] = aimArr[indexAim--];
else
aimArr[indexNew--] = insertArr[indexInsert--];
}
总结
综上所述，在合并数组（包括字符串）时，应该优先考虑从后往前复制。
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
