VIRTUALS

the virtual labs for the virtuals

0%

HJ26. 字符串排序

Posted on Edited on In , , ,

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

题目

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

规则 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. 字符串排序