剑指Offer:面试题4——替换空格(java实现)

问题描述:请实现一个函数,把字符串中的每个空格替换成”%20“。

例如:

输入:“We are happy.”

输出:”We%20are%20happy.”

思路1:按顺序找出空格所在的位置(下标),然后利用字串相加,将去除空格的字串用“%20”连接起来

/**
* 面试题4:替换空格
* @param str
* @return
*/
public static String replaceSpace(StringBuffer str){ String s = "";
int start = 0;
while(start >= 0){
int begin = start;
start = str.indexOf(" ", start);
if(start >= 0){
s = s + str.substring(begin, start) + "%20";
start++;
}else{
s = s + str.substring(begin, str.length());
break;
} } return s;
}

思路2:按照一般的想法,我们遍历字符,每遇到空格就将之替换,但是需要后面的字符的移动,这样做需要的移动次数很多。O(n^2)

思路3:基于思路2,我们移动的时候从后开始,这样就会减少很多重复的元素移动。

public static String replaceBlank(StringBuffer str){
if(str == null || str.length() < 0){ return null;
} int olength = str.length();
int nblank = 0; for(int i = 0; i < olength; i++){
if(str.charAt(i) == ' '){
nblank++;
}
} int newLength = olength + 2 * nblank; int increas = 2*nblank;
while(increas > 0){//此处是为了增加容量,不知道怎么用别的方法了
str.append(",");
increas--;
} System.out.println(str.length());
int indexOforiginal = olength-1;
int indexOfnew = newLength-1; while(indexOforiginal >= 0 && indexOfnew > indexOforiginal){
if(str.charAt(indexOforiginal) == ' '){
str.setCharAt(indexOfnew, '0');
indexOfnew--;
str.setCharAt(indexOfnew, '2');
indexOfnew--;
str.setCharAt(indexOfnew, '%');
indexOfnew--; }else{
str.setCharAt(indexOfnew, str.charAt(indexOforiginal));
indexOfnew--; } indexOforiginal--;
} return str.toString();
}
上一篇:剑指offer面试题4 替换空格(java)


下一篇:在Pycharm中配置Github