题目:
请实现一个函数,把字符串中的每个空格替换成“%20”,例如输入“We are happy”,则输出“We%20are%20happy”。
思路:
背景:
在网络编程中,如果URL参数中含有特殊字符,如空格,#等,导致服务器端无法获得正确的参数值,我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则就是在‘%’后面跟上ASCII码的两位十六进制的表示,比如空格的ASCII码是32,即十六进制的)0x20,因此空格被替换为“%20”。
方法:
1、假设可以开辟新的空间。
创建一新字符串,并在新字符串上面做空格替换。
时间复杂度:O(n),空间复杂度:O(n)
2、假设不能开辟新的空间,且原字符串长度足够。
- 从头到尾扫描字符串,每遇到空格字符时做替换,将1个字符替换为3个字符,因此空格后面的字符需要后移两个字符。
时间复杂度:O(n^2),空间复杂度:O(0)
- 从尾向头扫描字符串,每遇到空格字符时做替换,无需后移字符。首先遍历一遍字符串,统计字符串中空格的个数,并计算替换后字符串的总长度,每替换一个空格,长度增加2.替换时,准备两个指针P1,P2分别指向原始字符串的末尾和替换后字符串的末尾,依次移动指针P1,遇到空格做替换,直至P1和P2相遇,即前面不再有空格出现。
时间复杂度:O(n),空间复杂度:O(0)
代码:
#includeusing namespace std;void ReplaceBlank(char string[],int length){ if(string==NULL || length<=0) return; int originalLength=0; int numberOfBlank=0; int i=0; while(string[i]!='\0'){ ++originalLength; if(string[i]==' ') ++numberOfBlank; ++i; } int newLength=originalLength+numberOfBlank*2; if(newLength>length) return; int indexOfOriginal=originalLength; int indexOfNew=newLength; while(indexOfOriginal>=0 && indexOfNew>indexOfOriginal){ if(string[indexOfOriginal]==' '){ string[indexOfNew--]='0'; string[indexOfNew--]='2'; string[indexOfNew--]='%'; } else string[indexOfNew--]=string[indexOfOriginal]; --indexOfOriginal; }}int main(){ char sentence[100]="We are happy!"; ReplaceBlank(sentence,100); cout << sentence << endl; return 0;}
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/4060ac7e3e404ad1a894ef3e17650423?rp=1
AC代码:
class Solution {public: string replaceSpace(string str) { int originalLength=0; int numberOfBlank=0; int i=0; while(str[i]!='\0'){ ++originalLength; if(str[i]==' ') ++numberOfBlank; ++i; } int newLength=originalLength+numberOfBlank*2; //if(newLength>length) // return; int indexOfOriginal=originalLength; int indexOfNew=newLength; while(indexOfOriginal>=0 && indexOfNew>indexOfOriginal){ if(str[indexOfOriginal]==' '){ str[indexOfNew--]='0'; str[indexOfNew--]='2'; str[indexOfNew--]='%'; } else str[indexOfNew--]=str[indexOfOriginal]; --indexOfOriginal; } return str; }};