VIRTUALS

the virtual labs for the virtuals

0%

HJ26. 字符串排序

摘要:
经典的字符串排序问题。

题目

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

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

如,输入: $Type$ 输出: $epTy$

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

如,输入: $BabA$ 输出: $aABb$

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

如,输入: $By?e$ 输出: $Be?y$

注意有多组测试数据,即输入有多行,每一行单独处理(换行符隔开的表示不同行)

输入描述:
输入字符串

输出描述:
输出字符串

示例1

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

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

自定义排序 + 双指针

遍历字符串,将字母单独拿出来,用一个类/结构体维护每个字母的状态:字母本身,ascii码位置(判断是否大小写忽略时仍相同),数组下标。
再根据每个字母的状态自定义排序。
最后维护双指针,将剔出来的字母放回到字符串原位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* author: etoa
* code at: 2021年08月20日23:24:57
**/
#include <bits/stdc++.h>

using namespace std;

struct entity {
char c;
int ascii;
int idx;
};

inline bool cmp (entity a, entity b) {
if (a.ascii != b.ascii) return a.ascii < b.ascii;
return a.idx < b.idx;
}

inline void solve(string &s) {
int n = s.size();
vector<bool> st(n, false);

vector<entity> vec;
for (int i = 0, n = s.size(); i < n; i++) {
if (!isalpha(s[i])) {
st[i] = true;
} else {
entity ent;
ent.c = s[i];
ent.ascii = isupper(s[i]) ? s[i] + 32 : s[i];
ent.idx = i;
vec.push_back(ent);
}
}
sort(vec.begin(), vec.end(), cmp);
string res;
// double ptr
for (int i = 0, j = 0; i < n && j < n;) {
for (; i < n && st[i]; ++i) res += s[i];
for (; i < n && !st[i]; ++i, ++j) res += vec[j].c;
}
cout << res << endl;
}

int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
string s;
for (; getline(cin, s);) {
solve(s);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* author: etoa
* code at: 2021-08-20 23:52:36
**/
import java.util.*;

class Entity {
public char c;
public int ascii;
public int idx;
public Entity(char c, int ascii, int idx) {
this.c = c;
this.ascii = ascii;
this.idx = idx;
}
}

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for (; in.hasNext();) {
String s = in.nextLine();
int n = s.length();
boolean[] st = new boolean[n];
Arrays.fill(st, false);
List<Entity> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (!Character.isAlphabetic(c)) {
st[i] = true;
} else {
int ascii = Character.isUpperCase(c) ? c + 32 : c;
Entity ent = new Entity(c, ascii, i);
list.add(ent);
}
}
Collections.sort(list, new Comparator<Entity>(){
@Override
public int compare(Entity a, Entity b) {
if (a.ascii != b.ascii) return a.ascii - b.ascii;
else return a.idx - b.idx;
}
});
StringBuilder res = new StringBuilder();
for (int i = 0, j = 0; i < n && j < n;) {
for (; i < n && st[i]; ++i) res.append(s.charAt(i));
for (; i < n && j < n && !st[i]; ++i, ++j) res.append(list.get(j).c);
}
System.out.println(res.toString());
}
}
}

遍历字母表 + 双指针

这个解法思路奇特,按顺序遍历字母表,对于每个字母,如果其大写或小写在字符串中存在,就放到容器中,这样就可以做到按照字母顺序+下标顺序排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* author: etoa
* code at: 2021-08-21 00:29:23
**/
#include <bits/stdc++.h>

using namespace std;

int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
string s;
for (; getline(cin, s);) {
int n = s.size();
vector<char> alpha;
for (int i = 65; i < 91; i++) {
for (int j = 0; j < n; j++) {
if (s[j] == i || s[j] == i + 32) {
alpha.push_back(s[j]);
}
}
}
string res;
for (int i = 0, j = 0, len = alpha.size(); i < n; ++i) {
if (isalpha(s[i]) && j < len) res += alpha[j++];
else res += s[i];
}
cout << res << endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* author: etoa
* code at: 2021-08-21 00:37:28
**/
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for (; in.hasNext();) {
String s = in.nextLine();
int n = s.length();
List<Character> alpha = new ArrayList<>();
for (int i = 65; i < 91; i++) {
for (int j = 0; j < n; j++) {
char c = s.charAt(j);
if (c == i || c == i + 32) {
alpha.add(c);
}
}
}
StringBuilder res = new StringBuilder();
for (int i = 0, j = 0, len = alpha.size(); i < n; i++) {
if (!Character.isAlphabetic(s.charAt(i))) res.append(s.charAt(i));
else res.append(alpha.get(j++));
}
System.out.println(res.toString());
}
}
}

原题链接: HJ26. 字符串排序