剑指offer：替换空格

题目

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路

用"%20"三个字符来代替“ ”一个字符，字符串会变长，如果在原来的字符串上直接操作会导致后面的字符被覆盖，所以我们需要扩展空间；

如果创建新的字符串并在新的字符串上替换，则我们自己可以分配足够多的空间。这里我们采用的是在原来的字符串上替换，要将空格后面的字符串后移。

常规思路是从前向后遍历，碰到空格就将其后面的字符串后移两位，这样做的时间复杂度为O(n2)，但是仔细一看就可以发现后面很多字符是被重复移动的。

为了解决这个问题，我们采用从后向前遍历的方式，

首先遍历原字符串找出空格的数量m，则替换过后字符串的数量newLen为原字符串长度+2*m，将字符串空间扩展到newLen之后，从后向前遍历

原字符串，碰到非字符串则直接移动，遇到空字符串则替换。这种方式的时间复杂度为O（n）

代码

 1     public String replaceSpace(StringBuffer str) {
 2         if(str == null || "".equals(str)){
 3             return "";
 4         }
 5         int originLen = str.length();
 6         int blankNum = 0;
 7         for(int i=0; i<originLen;i++){
 8             if(str.charAt(i) == ' '){
 9                 blankNum++;
10             }
11         }
12         int currentLen = originLen+2*blankNum - 1;
13         str.setLength(currentLen+1);
14         for(int i=originLen-1;i>=0;i--){
15             char currentChar = str.charAt(i);
16             if(currentChar!=' '){
17                 str.setCharAt(currentLen, currentChar);
18                 currentLen--;
19             }else{
20                 str.setCharAt(currentLen--,'0');
21                 str.setCharAt(currentLen--,'2');
22                 str.setCharAt(currentLen--,'%');
23 
24             }
25         }
26         return str.toString();
27     }

扩展

合并两个排好序的数组A1，A2到A1中（A1后面有足够的空间可以容纳A2），使合并后的数组仍然有序

和上面同理，也是从尾到头遍历A1，A2找到A1,A2中尾部较大的数放到A1新的尾部，然后将较大数的数组的下标前移