Offer05（替换空格）

发表于 | 分类于 ，

题目：

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

思路：

　　最开始想到的思路是从头到尾遍历字符串，遇到字符串即替换，并插入%20，但字符串插入需要将后面的所有字符后移，算法复杂度较高。为优化时间复杂度，可以先统计出
替换空格后的字符串长度，然后从后到前插入。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 从前往后
public static String replaceSpace1(StringBuffer str) {
   	int i = 0;
   	while(i < str.length()) {
   		if (str.charAt(i) == ' ') {
			str.replace(i, i+1, "%");
			str.insert(i+1, "20");
		}
   		i++;
   	}
   	return str.toString();
   }
// 从后往前
public static String replaceSpace2(StringBuffer str) {
	int count = 0;
	for(int i = 0;i < str.length();i++) {
		if (str.charAt(i) == ' ') {
			count++;
		}
	}
	int newLength = count*2 + str.length();
	int p1 = str.length() - 1;
	int p2 = newLength - 1;
	str.setLength(newLength);
	while(p1 >=0 && p2 >= 0) {
		if (str.charAt(p1) == ' ') {
			str.setCharAt(p2--, '0');
			str.setCharAt(p2--, '2');
			str.setCharAt(p2--, '%');
			p1--;
		}else {
			str.setCharAt(p2, str.charAt(p1));
			p1--;
			p2--;
		}
	}
	return str.toString();
}

复杂度分析：

从前往后：

　　时间复杂度：
　　　　O(n**2)。
　　空间复杂度：
　　　　O(1)。

从后往前：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

总结：

　　在合并数组或者字符串时，如果从前往后需要重复移动后面数字，可以考虑从后往前进行合并。这样能减少数字移动的次数，大大增加效率。