【剑指Offer】2、替换空格
题目描述:
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路:
对于这个题目,我们首先想到原来的一个空格替换为三个字符,字符串长度会增加,因此,存在以下两种不同的情况:(1)允许创建新的字符串来完成替换。(2)不允许创建新的字符串,在原地完成替换。
第一种情况比较简单。对于第二种情况,有以下两种解法:
- 时间复杂度为O(n^2)的解法。
从头到尾遍历字符串,当遇到空格时,后面所有的字符都后移2个。 - 时间复杂度为O(n)的解法。
可以先遍历一次字符串,这样可以统计出字符串中空格的总数,由此计算出替换之后字符串的长度,每替换一个空格,长度增加2,即替换之后的字符串长度为原来的长度+2*空格数目。接下来从字符串的尾部开始复制和替换,用两个指针P1和P2分别指向原始字符串和新字符串的末尾,然后向前移动P1,若指向的不是空格,则将其复制到P2位置,P2向前一步;若P1指向的是空格,则P1向前一步,P2之前插入%20,P2向前三步。这样,便可以完成替换,时间复杂度为O(n)。
举例:
编程实现(Java):
//第一种情况:创建新的字符串实现:
public String replaceSpace(StringBuffer str) {
String res="";
for(int i=0;i<str.length();i++){
char c=str.charAt(i);
if(c==' ')
res += "%20";
else
res += c;
}
return res;
}
//第二种情况:原地替换,O(n)的解法
public String replaceSpace(StringBuffer str) {
if(str==null)
return null;
int numOfblank = 0;//空格数量
int len=str.length();
for(int i=0;i<len;i++){ //计算空格数量
if(str.charAt(i)==' ')
numOfblank++;
}
str.setLength(len+2*numOfblank); //设置长度
int oldIndex=len-1; //两个指针
int newIndex=(len+2*numOfblank)-1;
while(oldIndex>=0 && newIndex>oldIndex){
char c=str.charAt(oldIndex);
if(c==' '){
oldIndex--;
str.setCharAt(newIndex--,'0');
str.setCharAt(newIndex--,'2');
str.setCharAt(newIndex--,'%');
}else{
str.setCharAt(newIndex,c);
oldIndex--;
newIndex--;
}
}
return str.toString();
}
本题有实际的现实意义,在网络编程中,如果URL参数中含有特殊字符,则可能导致服务器端无法获得正确的参数值,因此可以通过替换的方法将其转换为可以识别的字符。转换规则就是%后面加上该字符ASCII码的16进制表示,如这里的空格,ASCII码是0x20(十进制的32),所以可以替换为%20。
标签:Offer,--,空格,str,字符串,替换,newIndex From: https://www.cnblogs.com/bujidao1128/p/17510279.html