由浅入深之字符串的算法题（vs: chatGPT做算法）

背景

俗话说，温故而知新。chatGPT效果太惊艳了！简直就是碾压的效果。但是还要有希望，先拾取，再创新。先了解，再超越吧。

ps: 再刷最后一遍算法题思路。顺便基于chatGPT3.5感受一下大模型的魔力。

字符串基础

C/C++每个字符串都以‘\0’作为结尾，这样就能很方便的找到字符串的最后尾部。由于这个特点，每个字符串都有一个额外字符的开销，稍不留神还会造成字符串的越界。如下，要想正确把0123456789复制到数组str中，需要声明一个长度为11字节的数组。

char str[10];
strcpy(str,"0123456789");

字符串数组与字符串指针

为节省内存，C/C++把常量字符串放在单独的一个内存区域。当几个指针赋值给相同的常量字符串时，他们实际会指向相同的内存地址。但是用常量内存初始化数组，情况却有所不同。

运行如下代码，会得到的结果是？

int main()
{char str1[]="hello world";char str2[]="hello world";char* str3="hello world";char* str4="hello world";if(str1==str2)printf("str1 and str2 are same.\n");elseprintf("str1 and str2 are not same.\n");if(str3==str4)printf("str3 and str4 are same.\n");elseprintf("str3 and str4 are not same.\n");return 0;    
}

str1和str2是两个字符串数组，我们会为它们分配两个长度为12字节的空间，并把“hello world”的内容分别复制到数组中去。这是两个初始地址不同的数组，因此str1和str2的值不相同。

str3和str4是两个指针，我们无须为它们分配内存以存储字符串的内容，而只需把它们指向“hello world”在内存中的地址就可以了。由于“hello world”是常量字符串，它在内存中只有一个拷贝，因此str3和str4的值相同。

算法题：替换空格

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

思路：看到这个题目，我们首先应该想到原来一个空格字符，替换后变成了'%', '2', '0'这3个字符，因此字符串会变长。如果在原来的字符串上进行替换，则有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串，并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。所以，要先明确出题者的需求。假如要在原字符串上进行替换，并保证输入的字符串后面有足够多的空余内存。

时间复杂度为O（n^2）的解法

最直观的做法是从头到尾扫描字符串，每次碰到空格字符的时候进行替换。由于把1个字符替换成3个字符，我们必须把后面所有字符都后移2字节，否则就会有2个字符被覆盖了。假设字符串的长度是n。对每个空格字符，需要移动后面O（n）个字符，因此对于含有O（n）个空格字符串而言，总的时间效率是O(n^2)。

时间复杂度为O（n）的解法

可以先遍历一次字符串，统计出字符串中空格的总数。然后从字符串的后面开始复制和替换。准备两个指针：p1和P2。P1指向原字符串的末尾，而P2指向替换之后的字符串的末尾。

接下来向前移动指针P1，逐个把它指向字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格之后，把p1向前移动一格，在P2之前插入字符串“%20”。由于“%20”的长度是3，同时把P2向前移动3格。如此P1接着向前复制，直到碰到第二个空格。当P1和P2指向同一个位置，表明所有空格都已经替换完毕。

这种算法所有的字符都只复制（移动）一次，因此这个算法的时间复杂度是O（n）。

/*length 为字符数组str的总容量，大于或等于字符串str的实际长度*/
void ReplaceBlank(char str[], int length)
{if(str == nullptr && length <= 0)return;/*originalLength 为字符串str的实际长度*/int originalLength = 0;int numberOfBlank = 0;int i = 0;while(str[i] != '\0'){++ originalLength;if(str[i] == ' ')++ numberOfBlank;++ i;}/*newLength 为把空格替换成'%20'之后的长度*/int newLength = originalLength + numberOfBlank * 2;if(newLength > length)return;int indexOfOriginal = originalLength;int indexOfNew = newLength;while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){if(str[indexOfOriginal] == ' '){str[indexOfNew --] = '0';str[indexOfNew --] = '2';str[indexOfNew --] = '%';}else{str[indexOfNew --] = str[indexOfOriginal];}-- indexOfOriginal;}
}