0.导引

作为软件程序员/工程师，对Java中默写字符串的特定替换应该都比较熟悉。而这都是以增加字符串的副本为前提的——String是不可变的，必须重新按照一定的规则重新赋值一份。

那现在有这样一个面试题要求：编写一个方法，用'%20'替换字符串中的所有空格。

您可以假设字符串末尾有足够的空间来容纳额外的字符，并且给定了字符串的“真实”长度，即两头除去空格的字符串。

示例如下：

输入字符串: "Ms Anny Smith ", （13个有效字符串，包括其中空格，后面的空格不计为有效字符数）。

输出字符串: "Ms%20Anny%20Smith" 。

1.解决思路

处理字符串操作问题的一种常见方法是从末尾开始向后编辑字符串。这是非常有用的，因为我们在末尾有一个额外的缓冲区，它允许我们更改字符而不用担心我们要覆盖的内容。

我们将在这个问题的解决办法中使用这种方法。该算法采用了两次扫描的方法。在第一次扫描中，我们计算空格的数量，即有效字符串中的空格。通过将这个数字翻三倍(原来的空格数再加上2倍的空格数)，我们可以计算出在最终字符串中有多少额外的字符（可以看作为字符串末尾的多余的空格数）。在第二步中，按照相反的顺序，即从后向前来实际上编辑该字符串，做字符的修改。当看到空格时，我们将其替换为“%20”三个字符。如果没有空格，则复制原始字符。

2.实现参考

public static void replaceSpaces(char[] str, int trueLength) {
		int spaceCount = 0, index, i = 0;
		for (i = 0; i < trueLength; i++) {
			if (str[i] == ' ') {
				spaceCount++;
			}
		}
		index = trueLength + spaceCount * 2;//这里是乘以二，而不是3，想想为什么
		if (trueLength < str.length)
			str[trueLength] = '\0'; // 有效字符数组结尾
		for (i = trueLength - 1; i >= 0; i--) {//"This is a String !        " 
			if (str[i] == ' ') {
				str[index - 1] = '0';
				str[index - 2] = '2';
				str[index - 3] = '%';
				index = index - 3;
			} else {
				str[index - 1] = str[i];
				index--;
			}
		}
	}

我们使用字符数组实现了这个问题，因为Java字符串是不可变的。如果我们直接使用字符串，函数将不得不返回一个新的字符串副本，但它将允许我们在一次传递中就实现这一点。但这不是作为面试算法相关问题的所关注的。

3.小结

作为面试官，我想这里主要是考考Java程序员的一些基本的算法性编程思维。Java中引用类型很多，但基本都是由8大基本类型复合构成的。如果要考虑一些特定的操作和效率，那肯定是原生数据类型更高效些。这里只是简单做个示例，以引起程序员的一点思考。

其实上面的小程序片段有点问题，你试试能不能找出明显的所在