【华为OD机试】HJ26 字符串排序

华为OD机试】HJ26 字符串排序"/>

【华为OD机试】HJ26 字符串排序

描述

编写一个程序，将输入字符串中的字符按如下规则排序。

规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。

如，输入： Type 输出： epTy

规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。

如，输入： BabA 输出： aABb

规则 3 ：非英文字母的其它字符保持原来的位置。
 

如，输入： By?e 输出： Be?y

数据范围：输入的字符串长度满足 1≤n≤1000 

输入描述：

输入字符串

输出描述：

输出字符串

示例1

输入：

A Famous Saying: Much Ado About Nothing (2012/8).

输出：

A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

思路：

根据三个规则，规则1要对字母进行排序，不区分大小写，这个通过sort函数加重写cmp完成，规则2要按照输入时的顺序进行排序，那么就要记录这个字母的位置，可以用结构体完成，规则3就直接把非字母跳过就行。

代码：

#include<bits/stdc++.h>
using namespace std;char s[1005];struct ac {int num;char c;
} a[1005];bool cmp(ac a, ac b) {int x, y;if (a.c >= 'a' && a.c <= 'z')x = a.c - 'a';elsex = a.c - 'A';if (b.c >= 'a' && b.c <= 'z')y = b.c - 'a';elsey = b.c - 'A';if (x == y)return a.num < b.num;elsereturn x < y;
}int main() {int  i, j = 0, k = 0;string str;getline(cin, str);for (i = 0; i < str.length(); i++) {if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z' ) {a[j].c = str[i];a[j].num = i;j++;}}sort(a, a + j, cmp);for (i = 0; i < str.length(); i++) {if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z' ) {cout << a[k].c;k++;} elsecout << str[i];}return 0;
}