力扣对应链接：LCR 122. 路径加密 - 力扣（LeetCode）
牛客对应链接：替换空格_牛客题霸_牛客网 (nowcoder.com)
核心考点 ：字符串相关，特性观察，临界条件处理。
一、《剑指Offer》内容
二、分析问题
虽然是替换问题，但是生成的字符串整体变长了。因替换内容比被替换内容长，所以一定涉及到字符串中字符的移动问题。移动方向一定是向后移动，所以现在的问题无非是移动多少的问题。
因为是 ' ' -> "%20"，是 1 换 3，所以可以先统计原字符串中空格的个数（设为 n），然后可以计算出新字符串的长度。所以，new_length = old_length + 2*n
最后，定义新老索引（或者指针），各自指向新老空间的结尾，然后进行 old->new 的移动。如果是空格，就连续放入“%20”，其他平移即可。
当然，C++ 有很多容器，也可以从前往后通过开辟空间来进行解决，也就是使用空间来换取时间。但是，最好不要在面试场景下这么做。
三、代码
//力扣上的这道题目是1换1，不需要扩充数组 class Solution { public: string pathEncryption(string path) { for(int i=0; i<path.size(); i++) if(path[i]=='.') path[i]=' '; return path; } }; //牛客网上的这道题目和原题也不太一样，这里传入的是string，原题是char* class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { string res; for(int i=0; i<s.size(); i++) { if(s[i]==' ') res+="%20"; else res+=s[i]; } return res; } }; //下面写法尽量贴近原题（注意：原题是char*，C++要考虑'\0'） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { if(s.size()==0) return s; int cnt=0; //记录空格个数 for(auto c:s) { if(c==' ') cnt++; } int old_end=s.size()-1; for(int i=0; i<cnt*2; i++) s.push_back(' '); int new_end=s.size()-1; while(old_end>=0 && new_end>=0) { if(s[old_end]==' ') { s[new_end--]='0'; s[new_end--]='2'; s[new_end--]='%'; old_end--; } else { s[new_end--]=s[old_end--]; } } return s; } };
四、扩展
有两个排序的数组 A1 和 A2，内存在 A1 的末尾有足够多的空余空间容纳 A2。请实现一个函数，把 A2 中的所有数字插入到 A1 中并且所有的数字是排序的。
和前面的例题一样，首先想到的办法可能是从前到尾复制数字，但这样就会出现多次复制一个数字的情况。
更好的办法是从尾到头比较 A1 和 A2 中的数字，并把较大的数字赋值到 A1 的合适位置。
C 库函数中内存拷贝 memmove() 函数与此题有共同点，函数功能就是：将起始地址 src 且长度为 count 的内存拷贝到起始地址 dst 处，并返回 dst，返回是为了实现链式表达式。
函数原型为：
void* __cdecl memmove(void *dst, const void *src, size_t count;
五、举一反三
合并两个数字（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。
