给定一个字符串，实现一个函数把字符串中的每个空格替换成 '%20'。

书中给出了时间为O(n)的算法：

1. 先遍历字符串长度，得到总长和空格数
2. 计算替换后的字符串总长度
3. 双指针实现从尾部向前替换

void replace_blank(char str[]){
    if(str == NULL)
	return;
    //1. get input char array length 
    int str_length = strlen(str)+1;
    //cout<<str_length<<endl;
    cout<<"Original char array : ";
    printf("%s\n", str);
    
    //2. new char array length should be str_length + 2*num_blanks
    int num_blanks =0;
    for(int i=0; i<str_length; i++){
	// get num_blanks
	if(str[i] ==' '){
	    num_blanks++;
	}
    }
    //cout<<num_blanks<<" blanks are found"<<endl;
    int new_str_length = str_length + 2*num_blanks;
    
    // create a new char array with new length
    char new_str[new_str_length];
    strcpy(new_str, str);
    //3. two relative address tracers  :
    // idx1 is the index of the end of original str
    // idx2 is the index of the end of new str
    int idx1 = str_length; //The last char is stored at Memory addr: (int&)str+str_length 
    int idx2 = new_str_length;
    while(idx1 >= 0 && idx2 > idx1){
	if(new_str[idx1] != ' '){
	    // copy the non-blank char back 
	    new_str[idx2--] = new_str[idx1];
      	}else{
	    // replace ' ' with '%''2''0' from back to front
	    new_str[idx2--] ='0';
	    new_str[idx2--] ='2';
	    new_str[idx2--] ='%';
	}	
	idx1--;
    }
    cout<<"Replace "<<num_blanks<<" blanks with %20 :";
    printf("%s\n", new_str);
}

完整程序：

git clone https://github.com/zhutiti/Hehaitao.git