剑指offer之把字符串里面空格替换成百分之20[时间复杂度是O(n)]

1 问题

把字符串里面空格替换成20%

要求：时间复杂度是O(n)

2 思路

比如我们字符串ab cd ef,我们先计算出新字符串需要的长度，我们分别搞2个指针指向老的和新的字符串的尾巴，然后老字符串从'\0'开始拷贝数据到新的字符串尾巴,同时两个指针同时左移，如果老的字符串遇到了空格，那么老的字符串指针往左边移动一格，然后新的字符串指针依然向左移动并且填充'0' 、'2'、 '%'，直到老的字符串指针到最左边或者老的字符串指针和新的字符串指针相等就不循环了

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     

      #include <string.h> 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//先得到多少个空格
     
    
   

    

     

    
    

     
	char *p = a;
     
    
   

    

     

    
    

     
	//先得到多少个空格
     
    
   

    

     

    
    

     
	int count = 0;
     
    
   

    

     

    
    

     
	int oldLen = 0;
     
    
   

    

     

    
    

     
	while (*p != '\0')
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (*p == ' ')
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			++count;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		++p;
     
    
   

    

     

    
    

     

      		++oldLen;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//计算新的字符串长度
     
    
   

    

     

    
    

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

    

     

    
    

     
	printf("oldLen is %d\n", oldLen);
     
    
   

    

     

    
    

     
	printf("newLen is %d\n", newLen);
     
    
   

    

     

    
    

     
	if (newLen > len)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("数组的长度不够\n");
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//循环条件也就是需要移动的数组下标最左边
     
    
   

    

     

    
    

     
	while (oldLen >= 0) //或加上while(oldLen >=0 && oldLen < newLen)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		//if (*(a + oldLen) != ' ')和下面的if等价
     
    
   

    

     

    
    

     
		if (a[oldLen] != ' ')
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			//这里用这个和下面的等价
     
    
   

    

     

    
    

     
			/**
     
    
   

    

     

    
    

     

       *(a + newLen) = *(a + oldLen);
     
    
   

    

     

    
    

     

       newLen--;
     
    
   

    

     

    
    

     

       oldLen--;
     
    
   

    

     

    
    

     

       **/
     
    
   

    

     

    
    

     

      			a[newLen--] = a[oldLen--];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			oldLen--;
     
    
   

    

     

    
    

     

      			a[newLen--] = '0';
     
    
   

    

     

    
    

     

      			a[newLen--] = '2';
     
    
   

    

     

    
    

     

      			a[newLen--] = '%';
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//这里给出数组的大小长度不能小于空格替换%20后
     
    
   

    

     

    
    

     
	//新的数组的长度,我们后面的函数需要做出处理
     
    
   

    

     

    
    

     
	char a[20] ="ab cd ef";
     
    
   

    

     

    
    

     
	int len = sizeof(a);
     
    
   

    

     

    
    

     
	int result = insert(a, len, "%20", 3);
     
    
   

    

     

    
    

     
	if (result != 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("insert fail\n");
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

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

    

     

    
    

     
	printf("区分strlen和sizeof\n");
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	char c[] = "abc";
     
    
   

    

     

    
    

     
	char d[3] = "abc";
     
    
   

    

     

    
    

     
	char e[4] = "abc";
     
    
   

    

     

    
    

     
	char *p = "abc";
     
    
   

    

     

    
    

     
	printf("sizeof(c) is %d\n", sizeof(c));
     
    
   

    

     

    
    

     
	printf("sizeof(d) is %d\n", sizeof(d));
     
    
   

    

     

    
    

     
	printf("sizeof(e) is %d\n", sizeof(e));
     
    
   

    

     

    
    

     
	printf("sizeof(p) is %d\n", sizeof(p));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("strlen(c) is %d\n", strlen(c));
     
    
   

    

     

    
    

     
	printf("strlen(d) is %d\n", strlen(d));
     
    
   

    

     

    
    

     
	printf("strlen(e) is %d\n", strlen(e));
     
    
   

    

     

    
    

     
	printf("strlen(p) is %d\n", strlen(p));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      oldLen is 8
     
    
   

    

     

    
    

     

      newLen is 12
     
    
   

    

     

    
    

     

      chars is ab%20cd%20ef
     
    
   

    

     

    
    

     

      区分strlen和sizeof
     
    
   

    

     

    
    

     

      sizeof(c) is 4
     
    
   

    

     

    
    

     

      sizeof(d) is 3
     
    
   

    

     

    
    

     

      sizeof(e) is 4
     
    
   

    

     

    
    

     

      sizeof(p) is 8
     
    
   

    

     

    
    

     

      strlen(c) is 3
     
    
   

    

     

    
    

     

      strlen(d) is 3
     
    
   

    

     

    
    

     

      strlen(e) is 3
     
    
   

    

     

    
    

     

      strlen(p) is 3
     
    
  
 

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

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