面试题5：替换空格
题目要求：
实现一个函数，把字符串中的每个空格都替换成“%20”，已知原位置后面有足够的空余位置，要求改替换过程发生在原来的位置上。
思路：
首先遍历字符串求出串中空格的数量，求出替换之后字符串的总长度（每替换一个空格，长度加2）。做法是从字符串的后面向前复制和替换。有2个指针p1、p2，p1指向原字符串的尾，p2指向替换之后的字符串的尾。接下来向前移动指针p1，逐个的将p1指向的字符复制到p2指向的位置，碰到空格时，p1向前移动一格，在p2之前插入字符串"%20"，再将p2向前移动3个。当p1和p2指向同一位置时，表明所有空格都已经替换完成。优点：所有的字符只复制或是移动一次
package com.java.offer; /**
* @since 2019年2月13日 下午5:51:51
* @author xuchao
*
* 替换空格
* 把传入字符数组中的' '换成'%20',且传入数组保证有足够空间容纳修改后的字符
*/
public class P5_ReplaceSpaces { public static String replaceBlank(StringBuilder str) {
int blankCount = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
blankCount++;
}
}
int oldLength = str.length();
int newLength = oldLength + blankCount * 2;
str.setLength(newLength);
int oldIndex = oldLength - 1;
int newIndex = newLength-1;
while (oldIndex >= 0 && newIndex > oldIndex) {
if (str.charAt(oldIndex) == ' ') {
str.setCharAt(newIndex--, '0');
str.setCharAt(newIndex--, '2');
str.setCharAt(newIndex--, '%');
} else {
str.setCharAt(newIndex--, str.charAt(oldIndex));
}
--oldIndex;
}
return str.toString();
} public static void main(String[] args) {
StringBuilder str = new StringBuilder("we are happy ");
String s = replaceBlank(str);
System.out.println(s);
}
}
相似题目
有两个排序的数组A1和A2，内存在A1的尾部有足够多的空间去容纳A2。实现一个函数是A2插入A1是有序的，且时间复杂度最小。最后解的思路还是从尾部开始比较A1和A2，并把较大的数字复制到A1的合适位置，即第一次都到达自己的最终位置。故这类题目合并两个数组，如果从前往后复制每个数字需要重复移动数字多次，那么我们可以考虑从后往前复制，这样时间复杂度就会大大降低。