当前位置： 首页 > article >正文

【华为OD-E卷 - 字符统计及重排 100分（python、java、c++、js、c）】

article 2025/3/18 15:59:15

【华为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";
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏


http://www.kler.cn/a/589945.html

相关文章：

  • jmeter 循环控制器遍历列表中的数据
  • 20250317笔记本电脑在ubuntu22.04下使用acpi命令查看电池电量
  • test skills
  • 【数据分析】数据筛选与访问行列元素3
  • 2020年蓝桥杯第十一届CC++大学B组（第二次）真题及代码
  • 从被动响应到主动防御——IT 应急演练平台 v3.0.1 重构企业安全免疫系统
  • RPC是啥？
  • 图论part3｜101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题
  • Vue3项目匹配PC端和移动端---一套组件
  • MATLAB语言的编程竞赛
  • 沉浸式vr大空间打造，打造超真实的虚拟体验
  • 【教学类-43-25】20240311 数独3宫格的所有可能（图片版 12套样式，空1格-空8格，每套510张，共6120小图）
  • 配置 VSCode 的 C# 开发环境
  • Matlab 基于专家pid控制的时滞系统
  • Tree of Thought Prompting（思维树提示）
  • 如何在 K8s 内部实现安全的网络隔离？
  • 掌握Python项目的依赖管理：利用`venv`与`conda`高效创建虚拟环境
  • 深度解析ECharts.js：构建现代化数据可视化的利器
  • c++图论(一)之图论的起源和图的概念
  • 【MySQL】MySQL审计工具Audit Plugin安装使用