首页 > 代码库 > 【剑指offer】替换空格

【剑指offer】替换空格

题目描述:

请实现一个函数,把字符串的每个空格替换成"%20"。例如输入"We are happy.",则输出"We%20are%20happy.".


分析描述:

方法一:对于给定的字符串,可以从前往后遍历整个字符串,遇到第一个空格时,就用"%20"替换空格,并将后面的字符向后移动,遇到第二个空格时,继续用"%20"替换空格,并将其后面的字符向后移动,依次类推,直到遇到结束符‘\0‘。这种方法的优点是简单易懂,确定是后面的字符要移动不止一次,算法的时间复杂度为O(n*n)。

方法二:以相反的思路来思考这个问题,把从前向后替换改成从后向前替换。这样对于需要移动的字符,只需要移动一次即可。时间复杂度为O(n)。我们可以先遍历一次字符串,这样就能统计出字符串中空格的总数,并可由此计算出替换之后的字符串的总长度。


程序示例:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void replaceblank(char string[], int length);

int
main(int argc, char **argv)
{
	char string[1000] = "We are happy.";
	replaceblank(string, 1000);
	
	return -1;
}

void replaceblank(char string[], int length)
{
	if(string == NULL || length <= 0){
		printf("element fail.\n");	
		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--;
	}

	printf("string[1000] = %s\n", string);
}
编译后运行结果如下:

string[1000] = We%20are%20happy.


总结:

1、对于字符串来讲,反向思路,从后往前考虑字符串也是一种思路。

2、对于字符数组做为函数的参数时,其实传递的是指向数组第一个元素的指针。