面试题4

题目描述：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

输入：

每个输入文件仅包含一组测试样例。
对于每组测试案例，输入一行代表要处理的字符串。

输出：

对应每个测试案例，出经过处理后的字符串。

样例输入：

We Are Happy

样例输出：

We%20Are%20Happy

第一种思路：边读入边判断，时间复杂度O（n),空间复杂度O（1）（做题即可）

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using std::cin;
using std::cout;
using std::endl;
using std::string;
const int MAX = 1000000;
int main(){
//	string str;
	char ch;
	char str[ MAX ];	
	char s[ 5 ] = "%20";
	while( ( ch = getchar() ) && ch != '\n' ){
		if( ch == ' ' )
			printf( "%s", s );
		else
			printf( "%c", ch );
	}
	printf( "\n" );
return 0;
}

 

第二种思路：和第一种类似，先读入数据，然后从头遍历一遍。可以调用新的数组，时间复杂度为O（n),空间复杂度为O（2*n) = O（n).不行的话，时间复杂度为O（n^2);
第三种思路：可以理解为第二种的优化。先统计空格数目，然后从加上2*空格数就等于更换后的总长度。然后从后向前找空格，直到所有空格都被替换即可停止。时间复杂度为O(n)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
const int MAX = 10000005;
char str[MAX];

void ReplaceBlank(char *str, int Length){
	if (str == NULL && Length <= 0)
		return;
	int originalLength = 0;
	int numberBlank = 0;
	int i = 0;
	while (str[i] != '\0'){
		++originalLength;
		if (str[i] == ' ')
			++numberBlank;
		++i;
	}
	int newLength = originalLength + numberBlank * 2;
	if (newLength > MAX){
		return;
	}
	while (originalLength >= 0 && newLength >= originalLength){
		if (str[originalLength] == ' '){
			str[newLength--] = '0';
			str[newLength--] = '2';
			str[newLength--] = '%';
		}
		else{
			str[newLength--] = str[originalLength];
		}
		--originalLength;
	}
}

int main(){
	gets(str);
	ReplaceBlank(str, MAX);
	cout << str << endl;
	return 0;
}