【华为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";
}
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏