微软2014实习生及秋令营技术类职位在线测试--String reorder

aabbccdd
007799aabbccddeeff113355zz
1234.89898
abcdefabcdefabcdefaaaaaaaaaaaaaabbbbbbbddddddee

abcdabcd
013579abcdefz013579abcdefz
<invalid input string>
abcdefabcdefabcdefabdeabdeabdabdabdabdabaaaaaaa

解题思路：

关键是对字符串的熟练操作，若是自己不熟悉，一遍测试一遍写，就慢很多。

算法中用到的重要操作细节举例：

string str="abcdefg";

string::iterator iter=str.begin();

str.erase(iter); //执行这条语句，会删除字符 ‘a‘， 返回的指向下一个字符‘b‘的迭代器

cout<<*iter<<endl; //特别注意这里iter会指向字符  ‘b‘ 了

下面附上自己实现的一个代码，写的不好，望见谅

#include <iostream>
#include <cstdio> //包含语言重定向函数freopen的库
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;
bool valiade(char a){
	if((a>=‘a‘ && a<=‘z‘) ||(a>=‘0‘ && a<=‘9‘)){
		return true;
	}else{
		return false;
	}
}
int main(){
	freopen("input.txt","r",stdin); //重定向输入流
	//freopen("ouput.txt","w",stdout);
	string str;
	while(cin>>str){
		bool flag=true;
		sort(str.begin(),str.end());
		//cout<<str<<endl;
		string temp;
		while(!str.empty()){
			string::iterator iter=str.begin();
			char lastch=*(iter);
			if(!valiade(lastch)){
				flag=false;
				break;
			}
			temp += *iter;
			(str.erase(iter));
			for(string::iterator it=str.begin(); it < str.end();){ 
				if(!valiade(lastch)){
					flag=false;
					goto here;
				}
				if( *it != lastch ){
					temp += *it;
					lastch = *it;
					str.erase(it);
				}else{
					++it;
				}
			}
		}
here: 
		if(flag){
			cout<<temp<<endl;
		}else{
			cout<<"<invalid input string>"<<endl;
		}
		
	}
	return 0; 
}

自己又修改了一下，使代码更好看了些。 ^_^

#include <iostream>
#include <cstdio> //包含语言重定向函数freopen的库
#include <algorithm>
#include <string>
#include <iterator>
using namespace std;
bool valiade(char a){
	if((a>=‘a‘ && a<=‘z‘) ||(a>=‘0‘ && a<=‘9‘)){
		return true;
	}else{
		return false;
	}
}
int main(){
	freopen("input.txt","r",stdin); //重定向输入流
	//freopen("ouput.txt","w",stdout);
	string str;
	while(cin>>str){
		bool flag=true;
		sort(str.begin(),str.end());
		string temp;
		while(!str.empty()){
			string::iterator iter=str.begin();
			char lastch=‘ ‘;
			do{
				if( *iter != lastch){
					temp += *iter;
					lastch = *iter;
					str.erase(iter);
				}else{
					iter++;
				}
				if(!valiade(lastch)){// validate later
					flag=false;
					goto done;
				}
			}while(iter<str.end());
		}
done: 
		if(flag){
			cout<<temp<<endl;
		}else{
			cout<<"<invalid input string>"<<endl;
		}
	}
	return 0; 
}