9度1510(文字列)

タイトル1510:スペースの置換
時間制限:1秒
メモリ制限:128メガ
特殊問題:いいえ
コミット:2553
解決:677
タイトルの説明:文字列のスペースを「%20」に置き換える関数を実装してください.例えば、文字列がWe Are Happyである.置換後の文字列は、We%20 Are%20 Happyである.
入力:各入力ファイルには、テストサンプルのセットのみが含まれます.各テストケースのセットについて、処理する文字列を表す行を入力します.
出力:各テストケースに対応し、処理された文字列を出力します.
サンプル入力:We Are Happyサンプル出力:We%20 Are%20 Happy
 
問題解
本体の問題型は非常に一般的で、通常は左から右に順次移動して各要素を処理することができ、この過程で後続の要素を移動し、時間の複雑度はO(n^2)である.時間複雑度を低減するために,空間交換時間を犠牲にして,O(n)の時間複雑度を有する別の配列を追加的に開くことができる.よく考えてみると,右から左へ元の配列に基づいて処理を試みることができ,時間的複雑さはO(n)に効果的に低減でき,記憶空間を余分に開かない.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;

int main()
{
	string str;
	char ch[10000000];
	while(getline(cin,str))
	//while(gets(ch))
	{		
		int i,count=0,size=str.size();
		for(i=0;i<size;i++)
		{
			if(str[i]==' ')count++;
		}

		i=size-1;
		ch[i+1+count*2]=0;
		while(i>=0)
		{
			if(str[i]==' ')
			{
				ch[i+count*2]='0';
				ch[i+count*2-1]='2';
				ch[i+count*2-2]='%';
				count--;
			}
			else 
				ch[i+count*2]=str[i];
			i--;
		}
		printf("%s
",ch);
	}
	return 0;
}