【华为OD-E卷 - 字符统计及重排 100分（python、java、c++、js、c）】
【华为OD-E卷 - 字符统计及重排 100分（python、java、c++、js、c）】
题目
给出一个仅包含字母的字符串，不包含空格，统计字符串中各个字母（区分大小写）出现的次数，并按照字母出现次数从大到小的顺序。
输出各个字母及其出现次数。如果次数相同，按照自然顺序进行排序，且小写字母在大写字母之前
输入描述
- 输入一行，为一个仅包含字母的字符串
输出描述
- 按照字母出现次数从大到小的顺序输出各个字母和字母次数，用英文分号分隔，注意末尾的分号；
字母和次数间用英文冒号分隔
用例
用例一：
输入：
xyxyXX
输出：
x:2;y:2;X:2;
用例二：
输入：
abababb
输出：
b:4;a:3;
python解法
- 解题思路：
- 统计字符频次：
通过遍历输入字符串 text，使用字典 freq 统计每个字符的出现次数。
字典的键是字符，值是该字符的出现次数。
自定义排序：
使用 compare(x, y) 函数自定义排序规则：
第一优先级：按照字符出现次数降序排序（出现次数多的排前面）。
第二优先级：如果两个字符出现次数相同，按以下规则比较：
同类字符（均为小写或均为大写）：按字典序升序排序。
不同类字符（一个大写、一个小写）：小写字母排在前面，大写字母排在后面。
排序并格式化输出：
使用 sorted() 函数，将字符频次字典转换为列表并按 compare 规则排序。
通过列表推导式将排序后的字符频次转换为格式 字符:次数; 形式的字符串
使用到的算法
哈希表（字典）：用于统计字符频次，时间复杂度为 O(n)（n 为字符串长度）。
自定义排序（基于 cmp_to_key 的比较器）：
基于比较器的排序（cmp_to_key）：时间复杂度 O(m log m)，其中 m 为不同字符的数量。
排序规则：
先按出现次数降序排列。
频次相同情况下：
同类型字符（大写或小写）：按字典序升序排列。
不同类型字符（小写优先）。
字符串拼接：遍历排序后的列表并拼接结果，时间复杂度 O(m)
import functools
# 获取输入字符串
text = input()
def compare(x, y):
"""
自定义比较函数，用于排序字符频次表
:param x: (字符, 频次) 元组1
:param y: (字符, 频次) 元组2
:return: 负数（x < y）, 0（相等）, 正数（x > y）
"""
# 1. 先按出现次数降序排序
if x[1] != y[1]:
return y[1] - x[1]
# 2. 处理相同频次的字符：
# - 同类型字符（都小写或都大写），按字典序升序排列
if (x[0].islower() and y[0].islower()) or (x[0].isupper() and y[0].isupper()):
return 1 if x[0] > y[0] else -1
# 3. 小写字母排在前面，大写字母排在后面
return 1 if x[0].isupper() else -1
def result():
"""
计算字符频次，并按规则排序后格式化输出
:return: 格式化的结果字符串
"""
# 1. 统计字符频次
freq = {}
for ch in text:
freq[ch] = freq.get(ch, 0) + 1
# 2. 将字典转换为 (字符, 频次) 元组列表
freq_list = list(freq.items())
# 3. 使用自定义排序函数进行排序
freq_list.sort(key=functools.cmp_to_key(compare))
# 4. 拼接结果字符串
return "".join([f"{k}:{v};" for k, v in freq_list])
# 输出结果
print(result())
java解法
- 解题思路
- 字符频次统计
读取用户输入的字符串 input。
使用 TreeMap<Character, Integer> 统计字符串中各字符的出现次数：
TreeMap 具有自动排序功能，默认按照 字典序 排序键（字符）。
自定义排序
使用 PriorityQueue 进行 自定义排序：
第一优先级：按出现次数降序排序（频次越高，优先级越高）。
第二优先级（出现次数相同时）：
若两个字符 均为小写 或 均为大写，按字典序升序排列。
若一个字符为 小写，另一个为 大写，小写优先，大写在后。
格式化输出
依次从 PriorityQueue 取出字符及其出现次数，拼接成 字符:次数; 的格式字符串并返回
用到的算法
哈希表（TreeMap）：
用于 统计字符频次，时间复杂度为 O(n)（n 为字符串长度）。
由于 TreeMap 自动排序，默认 字典序 排序键（字符），但不影响自定义排序。
优先队列（PriorityQueue）：
维护一个 最大堆 进行 自定义排序，用于 按照频次降序排列，时间复杂度 O(m log m)（m 为不同字符数）。
排序规则：
按字符出现次数降序。
出现次数相同：
同类字符（均小写/均大写） 按 字典序升序 排列。
小写字母优先，大写字母在后。
字符串拼接（StringBuilder）：
由于 Java 中字符串拼接 String 需要新建对象，因此用 StringBuilder 优化。
复杂度 O(m)
import java.util.*;
public class Main {
public static void main(String[] args) {
// 读取输入字符串
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
scanner.close();
// 计算字符频次并输出结果
System.out.println(calculateFrequency(input));
}
public static String calculateFrequency(String input) {
// 1. 使用 TreeMap 统计字符频次，并按照字典序自动排序
TreeMap<Character, Integer> charCountMap = new TreeMap<>();
for (char ch : input.toCharArray()) {
charCountMap.put(ch, charCountMap.getOrDefault(ch, 0) + 1);
}
// 2. 使用优先队列（最大堆），根据自定义规则排序
PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>(
(a, b) -> {
// (1) 先按照字符出现次数降序排列
if (!a.getValue().equals(b.getValue())) {
return b.getValue() - a.getValue();
}
// (2) 出现次数相同时，按以下规则排序：
else {
// (2.1) 如果两个字符都是小写或都是大写，按字典序升序排序
if (Character.isLowerCase(a.getKey()) && Character.isLowerCase(b.getKey())) {
return a.getKey() - b.getKey();
}
if (Character.isUpperCase(a.getKey()) && Character.isUpperCase(b.getKey())) {
return a.getKey() - b.getKey();
}
// (2.2) 小写字母优先，大写字母在后
return Character.isLowerCase(a.getKey()) ? -1 : 1;
}
}
);
// 3. 将统计结果放入优先队列
queue.addAll(charCountMap.entrySet());
// 4. 依次取出排序后的字符和频次，拼接结果字符串
StringBuilder result = new StringBuilder();
while (!queue.isEmpty()) {
Map.Entry<Character, Integer> entry = queue.poll();
result.append(entry.getKey()).append(":").append(entry.getValue()).append(";");
}
// 5. 返回格式化字符串
return result.toString();
}
}
C++解法
- 解题思路
- 字符频次统计
读取输入字符串 input。
使用 map<char, int>（有序映射） 统计各字符的出现次数：
键（char）为字符，值（int）为出现次数。
map 默认按照 字典序排序 键（字符）。
自定义排序
将 map 转换为 vector<pair<char, int>>，以便使用 sort() 自定义排序：
第一优先级：按出现次数降序排序（频次高的字符排前）。
第二优先级（出现次数相同时）：
小写字母优先（islower()）。
同类字符（均为小写或均为大写） 按 字典序升序 排序。
格式化输出
遍历排序后的 vector，拼接成 字符:次数; 格式的字符串
使用到的算法
哈希表（map）：
统计字符频次，时间复杂度 O(n)（n 为字符串长度）。
map 采用 红黑树（RB-Tree） 实现，插入元素的复杂度 O(log m)，m 为不同字符数。
自定义排序（sort() + lambda）：
排序优先级：
按频次降序（O(m log m)）。
频次相同：
小写字母优先。
同类字符（小写/大写） 按 字典序升序。
字符串拼接（stringstream）：
stringstream 处理拼接，避免 string 频繁 + 操作（O(m)）
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
/**
* 计算字符频次并进行排序
* @param input 输入字符串
* @return 格式化后的频次字符串
*/
string calculateFrequency(const string& input) {
// 1. 使用 map 统计字符出现次数（按字典序自动排序）
map<char, int> charCountMap;
for (char ch : input) {
charCountMap[ch]++;
}
// 2. 将 map 转换为 vector，便于自定义排序
vector<pair<char, int>> entryList(charCountMap.begin(), charCountMap.end());
// 3. 自定义排序
sort(entryList.begin(), entryList.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
// (1) 先按出现次数降序排序
if (b.second != a.second) {
return b.second < a.second; // 频次高的排前面
}
// (2) 频次相同情况下：
// 小写字母优先
if (islower(a.first) && isupper(b.first)) {
return true;
}
if (isupper(a.first) && islower(b.first)) {
return false;
}
// 同类型字符（小写或大写）按字典序升序
return a.first < b.first;
});
// 4. 拼接结果字符串
stringstream result;
for (size_t i = 0; i < entryList.size(); ++i) {
result << entryList[i].first << ":" << entryList[i].second;
if (i != entryList.size() - 1) {
result << ";";
}
}
return result.str() + ";";
}
int main() {
// 读取输入字符串
string input;
getline(cin, input);
// 输出计算结果
cout << calculateFrequency(input) << endl;
return 0;
}
C解法
更新中
JS解法
读取用户输入的字符串 s。
使用 Map 统计各字符的出现次数：
Map 的键是字符，值是该字符的出现次数。
自定义排序
将 Map 转换为数组，使用 sort() 进行 自定义排序：
第一优先级：按出现次数降序排序（频次高的字符排前）。
第二优先级（出现次数相同时）：
若两个字符 同为小写或同为大写，按 字典序升序 排序（localeCompare()）。
若 一个大写、一个小写，小写字母排前，大写字母排后。
格式化输出
遍历排序后的数组，将字符及其出现次数拼接成 字符:次数; 格式的字符串
使用到的算法
哈希表（Map）：
用于统计字符频次，时间复杂度 O(n)（n 为字符串长度）。
Map 适用于 动态插入和查询。
自定义排序（sort() + 比较函数）：
排序优先级：
按出现次数降序（O(m log m)）。
频次相同时：
同类字符（小写/大写） 按 字典序升序（localeCompare()）。
小写字母优先，大写字母在后。
字符串拼接（map().join(‘’)）：
遍历排序数组并拼接字符串，时间复杂度 O(m)
const readline = require("readline");
// 创建标准输入/输出接口
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 监听标准输入，读取用户输入并计算结果
rl.on("line", (line) => {
console.log(getResult(line));
});
/**
* 计算字符频次，并进行自定义排序后格式化输出
* @param {string} s - 输入字符串
* @return {string} - 频次统计后的格式化字符串
*/
function getResult(s) {
// 1. 统计字符频次
const countMap = new Map();
for (let char of s) {
countMap.set(char, (countMap.get(char) || 0) + 1);
}
// 2. 将 Map 转换为数组，并进行排序
const sortedArr = Array.from(countMap).sort((a, b) => {
// (1) 先按出现次数降序排列
if (a[1] !== b[1]) {
return b[1] - a[1];
}
// (2) 频次相同时：
// (2.1) 同类型字符（都小写或都大写），按字典序升序
if (isSameCase(a[0], b[0])) {
return a[0].localeCompare(b[0]);
}
// (2.2) 小写字母优先，大写字母在后
return isUpper(a[0]) ? 1 : -1;
});
// 3. 格式化输出，拼接字符串
return sortedArr.map(([char, count]) => `${char}:${count};`).join('');
}
/**
* 判断两个字符是否是相同类型（均为大写或均为小写）
* @param {string} a - 字符1
* @param {string} b - 字符2
* @return {boolean} - 是否同为大小写
*/
function isSameCase(a, b) {
return (isUpper(a) && isUpper(b)) || (isLower(a) && isLower(b));
}
/**
* 判断字符是否为小写字母
* @param {string} letter - 字符
* @return {boolean} - 是否为小写字母
*/
function isLower(letter) {
return letter >= "a" && letter <= "z";
}
/**
* 判断字符是否为大写字母
* @param {string} letter - 字符
* @return {boolean} - 是否为大写字母
*/
function isUpper(letter) {
return letter >= "A" && letter <= "Z";
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏