1.题目描述：
请实现一个函数，把字符串中的每个空格替换成%20。例如，输入“we are happy.”，输出"we%20are%20happy."。
2.解题思路：
可以先遍历数组，统计出空格的个数，则新字符串的长度 = 旧字符串的长度 + 2 * 空格个数。然后使用双指针法，指针p1指向旧字符串的末尾，指针p2指向新字符串的末尾，从后往前进行拷贝。如果p1指向的字符为空格，则向p2所在的位置拷贝0、2、%，再递减指针。
3.代码实现：
public class Offer_5 {
public static void main(String[] args) {
String str = "we are happy.";
System.out.println(ReplaceBlack(str));
}
private static String ReplaceBlack(String str) {
int numOfBlack = 0;
int p1, p2;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
numOfBlack++;
}
}
p1 = str.length() - 1;
p2 = 2 * numOfBlack + str.length();
char[] result = new char[p2 + 1];
while (p1 >= 0 && p2 >= p1) {
if (str.charAt(p1) == ' ') {
result[p2--] = '0';
result[p2--] = '2';
result[p2--] = '%';
p1--;
} else {
result[p2--] = str.charAt(p1--);
}
}
return String.valueOf(result);
}
}
这个题如果要申请新的数组，其实用从前往后拷贝的方法也可以，若是输入参数为指针，则可以利用指针偏移的方式，不必再重新申请空间。
复杂度分析：
- 时间复杂度：O(n)，字符长度为n，则总的时间复杂度为O(n).
- 空间复杂度：O(n)，需要额外开辟长度为2n+空格个数大小的空间，总的空间复杂度为O(n)。
