解题思路

这是一道字符串字母排序问题,主要思路如下:

  1. 问题分析:

    • 将字符串中的字母按字典序排序
    • 保持非字母字符的位置不变
    • 保持字母的大小写不变
    • 需要处理多行输入
  2. 解决方案:

    • 先收集所有字母并按字典序排序
    • 保持原字符串中非字母字符的位置
    • 按顺序替换原字符串中的字母
    • 输出结果字符串
  3. 关键点:

    • 区分字母和非字母字符
    • 保持原有大小写
    • 维持非字母字符位置不变

代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        // 收集字母并排序
        vector<char> letters;
        
        // 按字母表顺序收集字母
        for (int i = 0; i < 26; i++) {
            for (char c : s) {
                if ((c - 'a' == i) || (c - 'A' == i)) {
                    letters.push_back(c);
                }
            }
        }
        
        // 替换原字符串中的字母
        int letterIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if ((s[i] >= 'a' && s[i] <= 'z') || 
                (s[i] >= 'A' && s[i] <= 'Z')) {
                s[i] = letters[letterIndex++];
            }
        }
        
        cout << s << endl;
    }
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            char[] chars = s.toCharArray();
            
            // 收集字母并排序
            ArrayList<Character> letters = new ArrayList<>();
            
            // 按字母表顺序收集字母
            for (int i = 0; i < 26; i++) {
                for (char c : chars) {
                    if ((c - 'a' == i) || (c - 'A' == i)) {
                        letters.add(c);
                    }
                }
            }
            
            // 替换原字符串中的字母
            int letterIndex = 0;
            for (int i = 0; i < chars.length; i++) {
                if ((chars[i] >= 'a' && chars[i] <= 'z') || 
                    (chars[i] >= 'A' && chars[i] <= 'Z')) {
                    chars[i] = letters.get(letterIndex++);
                }
            }
            
            System.out.println(new String(chars));
        }
    }
}
def sort_letters(s: str) -> str:
    # 收集字母并排序
    letters = []
    
    # 按字母表顺序收集字母
    for i in range(26):
        for c in s:
            if (ord(c.lower()) - ord('a') == i):
                letters.append(c)
    
    # 替换原字符串中的字母
    result = list(s)
    letter_index = 0
    
    for i in range(len(result)):
        if result[i].isalpha():
            result[i] = letters[letter_index]
            letter_index += 1
    
    return ''.join(result)

# 处理输入
while True:
    try:
        s = input()
        print(sort_letters(s))
    except EOFError:
        break

算法及复杂度

  • 算法:字符串处理
  • 时间复杂度: - 为字符串长度, 为字母表大小(26)
  • 空间复杂度: - 需要存储字母数组