3.二维数组中的查找
5. 逆序打印单向链表 Print linked list reversely using C++ class implementation

4.替换空格

Author posted @ 2013年10月03日 13:59 in 剑指Offer with tags c++ , 2415 阅读

给定一个字符串,实现一个函数把字符串中的每个空格替换成 '%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
seo 说:
2021年10月02日 12:33

https://www.digitekprinting.com/architectural-drawings is the one who printed out my business cards for my personal information that I give to my clients. I can say that the materials they used are extensive. Also, customization is available for you to choose your own style.

merckseo 说:
2021年10月10日 08:23

Best Social Plan is the most trusted company for providing social media marketing services. Within some years it has gained popularity as a reliable company to its customers. This company is now managing its activity successfully. It is proved number one company by its quality services. It is noticed that more and more customers are showing their intention to take service from this company. Best Social Plan

anonymous 说:
2023年7月28日 05:25

It is somewhat fantastic, and yet check out the advice at this treat. Kissimmee Termite Control

anonymous 说:
2023年8月04日 23:29

There you can download for free, see the first of these data.  Orlando Bed Bug Pest Control

anonymous 说:
2023年8月04日 23:31

I came onto your blog while focusing just slightly submits. Nice strategy for next, I will be bookmarking at once seize your complete rises... Oviedo Bed Bug Pest Control

anonymous 说:
2023年9月19日 01:44

In this case you will begin it is important, it again produces a web site a strong significant internet site: Trouver du bien-être à Montreux Vevey Territet Chardonne Saint-Legier Villeneuve Chatel-Saint-Denis

anonymous 说:
2023年9月22日 03:41

Such sites are important because they provide a large dose of useful information ...  iournalist101

anonymous 说:
2023年9月23日 01:00

Hi there, I discovered your blog per Google bit searching for such kinda educational advise moreover your inform beholds very remarkable for me. schwarzkümmel


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter