解题思路
这是一道字符串字母排序问题,主要思路如下:
-
问题分析:
- 将字符串中的字母按字典序排序
- 保持非字母字符的位置不变
- 保持字母的大小写不变
- 需要处理多行输入
-
解决方案:
- 先收集所有字母并按字典序排序
- 保持原字符串中非字母字符的位置
- 按顺序替换原字符串中的字母
- 输出结果字符串
-
关键点:
- 区分字母和非字母字符
- 保持原有大小写
- 维持非字母字符位置不变
代码
#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)
- 空间复杂度:
- 需要存储字母数组