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

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

注意:

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


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安装使用