マイクロソフト2014実習生オンラインテストのString reorder
問題の説明:
Time Limit: 10000ms Case Time Limit: 1000ms Memory Limit: 256MB Description For this question, your program is required to process an input string containing only ASCII characters between ‘0’ and ‘9’, or between ‘a’ and ‘z’ (including ‘0’, ‘9’, ‘a’, ‘z’). Your program should reorder and split all input string characters into multiple segments, and output all segments as one concatenated string. The following requirements should also be met, 1. Characters in each segment should be in strictly increasing order. For ordering, ‘9’ is larger than ‘0’, ‘a’ is larger than ‘9’, and ‘z’ is larger than ‘a’ (basically following ASCII character order). 2. Characters in the second segment must be the same as or a subset of the first segment; and every following segment must be the same as or a subset of its previous segment. Your program should output string “” when the input contains any invalid characters (i.e., outside the '0'-'9' and 'a'-'z' range). Input Input consists of multiple cases, one case per line. Each case is one string consisting of ASCII characters.
Output For each case, print exactly one line with the reordered string based on the criteria above. Sample In aabbccdd 007799aabbccddeeff113355zz 1234.89898 abcdefabcdefabcdefaaaaaaaaaaaaaabbbbbbbddddddee Sample Out abcdabcd 013579abcdefz013579abcdefz abcdefabcdefabcdefabdeabdeabdabdabdabdabaaaaaaa
基本的な考え方:
入力をループし、まず入力した文字列をソートし、同じ文字ごとに0から始まる昇順で識別し、出力ごとに識別を-1に設定します.最初の出力は0とマークされた文字です.
次に、ループ出力:
出力IDが正の文字であるたびに、IDを変更し、間隔が-1になってから出力を続行します.サイクル毎に出力される個数を記録し、0の場合に停止します.
コードは次のとおりです.
Time Limit: 10000ms Case Time Limit: 1000ms Memory Limit: 256MB Description For this question, your program is required to process an input string containing only ASCII characters between ‘0’ and ‘9’, or between ‘a’ and ‘z’ (including ‘0’, ‘9’, ‘a’, ‘z’). Your program should reorder and split all input string characters into multiple segments, and output all segments as one concatenated string. The following requirements should also be met, 1. Characters in each segment should be in strictly increasing order. For ordering, ‘9’ is larger than ‘0’, ‘a’ is larger than ‘9’, and ‘z’ is larger than ‘a’ (basically following ASCII character order). 2. Characters in the second segment must be the same as or a subset of the first segment; and every following segment must be the same as or a subset of its previous segment. Your program should output string “
Output For each case, print exactly one line with the reordered string based on the criteria above. Sample In aabbccdd 007799aabbccddeeff113355zz 1234.89898 abcdefabcdefabcdefaaaaaaaaaaaaaabbbbbbbddddddee Sample Out abcdabcd 013579abcdefz013579abcdefz
基本的な考え方:
入力をループし、まず入力した文字列をソートし、同じ文字ごとに0から始まる昇順で識別し、出力ごとに識別を-1に設定します.最初の出力は0とマークされた文字です.
次に、ループ出力:
出力IDが正の文字であるたびに、IDを変更し、間隔が-1になってから出力を続行します.サイクル毎に出力される個数を記録し、0の場合に停止します.
コードは次のとおりです.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
int *a;
while ( cin >> str ) {
int size_str = str.size();
sort(str.begin(), str.end());
bool invalid = false;
for ( int i = 0 ; i < size_str ; i ++) {
if ( !(((str[i] >= '0')&&(str[i] <= '9')) || ((str[i] >= 'a')&&(str[i] <= 'z')))) {
cout << "<invalid input string>
";
invalid= true;
break;
}
}
if ( invalid == true ) continue;
a = new int [size_str];
a[0] = 0;
for ( int i = 1 ; i < size_str ; i++) {
a[i] = ( str[i] != str[i-1] ) ? 0 : a[i-1] + 1;
}
int count = 0 ;
for ( int i = 0 ; i < size_str ; i ++) {
if ( a[i] == 0 ) {
cout << str[i];
a[i] = -1;
count ++;
}
}
bool out_permit = false;
while ( count != 0 ) {
count = 0 ;
for ( int i = 0 ; i < size_str ; i ++) {
if ( a[i] < 0 ) out_permit = true;
if ( a[i] > 0 && out_permit ) {
cout << str[i];
a[i] = -1;
out_permit = false;
count++;
}
}
}
cout << endl;
delete [] a;
}
return 0;
}