抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

替换空格符

题目: 请实现一个函数, 把字符串中的每个空格替换成针%20″。例如 “We are happy.”, 则输出 “We%20are%20happy.”。

在网络编程中,如果 URL 参数中含有特殊字符, 如空格、’#’等, 可能导致服务器端无法获得正确的参数值。 我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在’%’后面跟上 ASCII 码的两位十六进制的表示。 比如空格的 ASCII 码是 32, 即十六进制的 0x20, 因此空格被替换成”%20″。再比如’#’的 ASCII 码为 35, 即十六进制的 0x23, 它在 URL 中 被替换为”%23″。

常规解:

最直观的做法是从头到尾扫描字符串, 每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符,我们必须要把空格后面所有的字符都后移两个字节, 否则就有两个字符被覆盖了。

假设字符串的长度是n。对每个空格字符,需要移动后面O(n)个字符, 因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。

更优解:

我们可以先遍历一次字符串, 这样就能统计出字符串中空格的总数, 并
可以由此计算出替换之后的字符串的总长度。 每替换一个空格, 长度增加2,因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们还是以前面的字符串”We are happy.”为例,”We are happy.”这个字符串的长度是14(包括结尾符号’\O’), 里面有两个空格,因此替换之后字符串的长度是18。我们从字符串的后面开始复制和替换。 首先准备两个指针,P1 和 P2。 P1指向原始字符串的末尾, 而P2 指向替换之后的字符串的末尾(如图2.4),接下来我们向前移动指针 P1逐个把它指向的字符复制到P2
指向的位置,直到碰到第一个空格为止。碰到后,P1向前移动1格, 在P2 之前插入字符串”%20″。 由于”%20″的长度为3, 同时也要把P2向前移动3格。

我们接着向前复制, 直到碰到第二个空格。和上一
次一样,我们再把P1向前移动1格, 并把P2向前移动3格插入”%20″,此时P1和P2指向同一位置,表明替换完成。

从上面的分析我们可以看出,所有的字符都只复制(移动)一次,此这个算法的时间效率是O(n),比第一个要快。

代码实现:

public static String replaceSpace(StringBuffer str) {
if (str == null || str.toString().length() <= 0) {
return "";
}

char[] chars = str.toString().toCharArray();

int blankNums = 0;

for (char s : chars) {
if (s == ' ') {
blankNums++;
}
}

char[] newStr = new char[chars.length + blankNums * 2];

int oriStrPos = chars.length - 1;
int newStrPos = newStr.length - 1;

while (oriStrPos >= 0 && newStrPos >= oriStrPos) {

if (chars[oriStrPos] == ' ') {
newStr[newStrPos--] = '0';
newStr[newStrPos--] = '2';
newStr[newStrPos--] = '%';
} else {
newStr[newStrPos--] = chars[oriStrPos];
}
oriStrPos--;
}

return new String(newStr);
}


0条评论

发表评论