[华为OJ题解]特殊要求字符串排序

本题是一个简单排序的题目,但是题目中对于不同字符给予不同的处理,稍微麻烦一点。主要涉及大小写忽略的稳定排序。输出的时候要固定非字母字符的位置等知识点。

题目要求如下:
规则1:英文字母从A到Z排列,不区分大小写。
      如,输入:Type 输出:epTy
规则2:同一个英文字母的大小写同时存在时,按照输入顺序排列。
    如,输入:BabA 输出:aABb
规则3:非英文字母的其它字符保持原来的位置。
    如,输入:By?e 输出:Be?y
样例:
    输入:
   A Famous Saying: Much Ado About Nothing(2012/8).
    输出:
   A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

对于大小写不敏感,可以在比较函数中,将所有字符转化为小写然后再比较即可。对于非英文字母保持原位置不变,我们可以遍历原有字符串,对于非英文字母我们直接输出,而对于英文字母,那我们应该从已排序字符串中寻找下一个英文字母。

代码如下:

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdio>

using namespace std;

bool cmp(char ca, char cb)
{
	char ta = tolower(ca);
	char tb = tolower(cb);

	return ta < tb;
}

int main()
{
	string s;

	getline(cin, s);


	string ts(s);

	stable_sort(ts.begin(), ts.end(), cmp);

	
	int len = s.length();
	int idx = -1;

	for (int i = 0; i < len; ++i)
	{
		if (isalpha(s[i]))
		{
			++idx;
			while (!isalpha(ts[idx]))
			{
				++idx;
			}
			cout << ts[idx];
		}
		else
		{
			cout << s[i];
		}
	}
	
	cout << endl;
	

	return 0;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[华为OJ题解]特殊要求字符串排序

本文链接地址:http://www.iaccepted.net/algorithm/hwoj/124.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注