数据结构OJ--字符串变形

对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

比如"Hello World"变形后就变成了"wORLD hELLO"。

数据范围: 1≤n≤10^6 , 字符串中包括大写英文字母、小写英文字母、空格。进阶：空间复杂度 O(n) ， 时间复杂度 O(n)

输入：

给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)

输出：

请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

输入样例 1

This is a sample
16

输出样例 1

SAMPLE A IS tHIS

解题思路：（1）难实现思路（字符串的 *** 作）：首先输入一串字符串并用字符数组存储，并对数组中的空格进行标记。然后再将其倒置存储，即将”hello world“转为”DLLOW OLLEH“，然后遍历该数组，遇到空格则再进行倒置，即为”WOLLD HELLO"，程序写出来了，但是死活过不了oj。

（2）简单栈 *** 作（思路来源于美丽的总裁）：再永真循环（循环结束条件为读取到回车）中，将空格作为分界符，当a[i]读取到空格时即退出输入，并将a[i]中的元素从尾至头入栈并改变大小写，然后将a[i]初始化，当a[i]读取到回车时，退出永真循环，并将栈中元素出栈并输出，不得不说，总裁真是太聪明了！

#include
#define maxsize 10000
using namespace std;
typedef struct{
	char *base;
	char *top;
	int stacksize;
}Sqstack;
void CreatSqstack(Sqstack &S){
	S.base=new char[maxsize];
	S.top=S.base; 
	S.stacksize=maxsize;

}

void push(Sqstack &S,char *a,int n){
	int i;
	for(i=n-1;i>=0;i--){
		if(a[i]>='a'&&a[i]<='z')
			*S.top++=a[i]-32;
		else if(a[i]>='A'&&a[i]<='Z')
			*S.top++=a[i]+32;
	}
	*S.top++=' ';
}
void pop(Sqstack &S){
	S.top--;
	while(S.base!=S.top)
		cout<<*--S.top;
}

int main(){
	Sqstack S;
	char a[30];
	int i=0,flag=0,n;
	CreatSqstack(S);
	while(1){
		i=0;
		a[i]=getchar();
		while(a[i]!=' '){
			if(a[i]=='\n'){
				flag=1;
				break;
			}
			i+=1;
			a[i]=getchar();
		}
		a[i]=' ';
		push(S,a,i);
		if(flag) break;	
	}
	cin>>n;
	pop(S);	
	delete S.base;
	return 0;
}