剑指offer之把字符串里面空格替换成百分之20

1 问题

把字符串里面空格替换成百分之20

2 代码实现

第一种时间复杂的o(n * n)实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      char* insert(char *a, int len, char *replace, int replaceLen)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//先得到多少个空格
     
    
   

    

     

    
    

     
	char *p = a;
     
    
   

    

     

    
    

     
	int count = 0;
     
    
   

    

     

    
    

     
	while (*p != '\0')
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (*p == ' ')
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			++count;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		++p;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//计算新的字符串长度
     
    
   

    

     

    
    

     
	int newLen = len + count * (replaceLen - 1);
     
    
   

    

     

    
    

     
	char *newP = NULL;
     
    
   

    

     

    
    

     

      	newP = (char *)malloc(newLen);
     
    
   

    

     

    
    

     
	if (!newP)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("malloc fail\n");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//新开辟内存的指针后面操作的时候
     
    
   

    

     

    
    

     
	//我们用新的指针变量保存新开辟内存的指针
     
    
   

    

     

    
    

     
	char *new = newP;
     
    
   

    

     

    
    

     
	//尽量不要修改原始字符串的指针位置
     
    
   

    

     

    
    

     
	char *head = a;
     
    
   

    

     

    
    

     
	//尽量不要修改原始需要替换字符串的位置
     
    
   

    

     

    
    

     
	char *rep = replace;
     
    
   

    

     

    
    

     
	while(*head != '\0')
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (*head != ' ')
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			*new++ = *head++;	
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			*head++;
     
    
   

    

     

    
    

     
			while (*rep != '\0')
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       *new++ = *rep++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			//这里要记得移动指针完了之后复原替换字符串指针
     
    
   

    

     

    
    

     

      			rep = replace; 
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 //尾巴要记得设置'\0'
     
    
   

    

     

    
    

     

       *new = '\0';
     
    
   

    

     

    
    

     
	//这里是申请了哪个内存指针就返回哪个
     
    
   

    

     

    
    

     
	//千万不要移动这个新开辟内存的指针
     
    
   

    

     

    
    

     
	//不然后面进行free(newP)就有问题
     
    
   

    

     

    
    

     
	return newP;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	char a[] ="ab cd ef";
     
    
   

    

     

    
    

     
	int len = sizeof(a);
     
    
   

    

     

    
    

     
	char *chars = insert(a, len, "%20", 3);
     
    
   

    

     

    
    

     
	printf("chars is %s\n", chars);
     
    
   

    

     

    
    

     
	free(chars);
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      }
     
    
  
 

3 运行结果

chars is ab%20cd%20ef
 

4 总结

1  在函数里面，如果我们新开辟内存的指针如果要返回，我们不要移动这个指针的位置，不然到时外面得到了开辟内存移动后的指针进行free的时候，会出问题，所以我们要用个指针变量保存这个新开辟内存的指针，然后用指针变量进行操作内存数据

2 在函数里面如果参数传递的是指针，我们尽量不要移动，用个指针变量保存函数参数里面的指针，然后用指针变量进行内存数据操作

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/86544701