华为OD机试 - 计算误码率（Python/JS/C/C++ 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

误码率 是最常用的数据通信传输质量指标。它可以理解为“在多少位数据中出现一位差错”。

移动通信 网络中的误码率主要是指比特误码率，其计算公式如下：比特误码率 = 错误比特数 / 传输总比特数，为了简单，我们引入字符串来表示误码通信的信息，一个字符错误了，就认为出现了一个误码。

输入一个标准的字符串，和一个传输前的字符串，计算误码率。

字符串会被压缩，例如：“2A3B4D5X1Z"表示”AABBBBDDDDXXXXXZ”

用例保证两个输入字符串解压后后长度一致，解压前后的长度不一定一致。

每个生成后的字符串长度 < 1000000。

二、输入描述

两行，分别为两种字符串的压缩形式。

每行字符串（压缩后的）长度 < 1000000。

三、输出描述

一行，错误的字母数量 / 展开后的总长度

备注

注意：展开后的字符串不会为数字。

四、测试用例

测试用例1：

1、输入

3A3B 2A4B

2、输出

1/6

3、说明

第一个字符串 “3A3B” 解压为 “AAABBB”。

第二个字符串 “2A4B” 解压为 “AABBBB”。

两个解压后的字符串逐一比较，共有 6 个字符。

发现 1 个位置的字符不同（第 3 个字符），误码数为 1。

误码率 = 错误的字符数量 / 总字符长度 = 1 / 6。

测试用例2：

1、输入

5Y5Z 5Y5Z

2、输出

0/10

3、说明

两个压缩字符串 “5Y5Z” 解压后都为 “YYYYYZZZZZ”。

两个解压后的字符串完全相同，没有错误字符。

误码率 = 0 / 10，所以输出 0/10。

五、解题思路

1、题目理解

题目给出两个经过压缩编码的字符串，通过解压缩后需要判断两个字符串在解压后的误码率，即对应位置不同的字符数量占总字符数量的比例。

输入的字符串是压缩形式，例如 “2A3B” 表示 “AABBB”。我们需要将这两个压缩字符串解压成实际的字符序列，然后逐位比较它们，统计误码（不同字符）的数量。

2、具体步骤：

1. 解压缩字符串:
   • 将压缩的字符串解压成实际的字符串序列。
   • 压缩字符串的格式为：数字+字母的组合，表示字母重复的次数，例如 “3A4B” 解压后为 “AAABBBB”。
   • 由于数字可能是多位的，例如 “12A” 表示 “AAAAAAAAAAAA”，所以需要处理多位数字。
2. 比较两个解压后的字符串:
   • 比较解压后的两个字符串，统计它们在每个位置上的不同字符数（误码）。
3. 计算误码率:
   • 误码率的公式为：错误的字符数量 / 解压后的总长度。

六、Python算法源码

def decompress(compressed):
    # 解压缩字符串
    expanded = []
    i = 0
    n = len(compressed)
    
    while i < n:
        num = 0
        # 解析数字部分，可能有多位数字
        while i < n and compressed[i].isdigit():
            num = num * 10 + int(compressed[i])
            i += 1
        # 当前字符是要重复的字符
        if i < n:
            ch = compressed[i]
            # 重复添加字符
            expanded.append(ch * num)
            i += 1

    return ''.join(expanded)

def main():
    # 读取输入
    compressed1 = input().strip()
    compressed2 = input().strip()

    # 解压两个字符串
    expanded1 = decompress(compressed1)
    expanded2 = decompress(compressed2)

    # 计算误码数量
    error_count = 0
    total_length = len(expanded1)  # 根据题目，长度相同

    for i in range(total_length):
        if expanded1[i] != expanded2[i]:
            error_count += 1

    # 输出结果
    print(f"{error_count}/{total_length}")

if __name__ == "__main__":
    main()

七、JavaScript算法源码

function decompress(compressed) {
    // 解压缩字符串
    let expanded = [];
    let i = 0;
    let n = compressed.length;

    while (i < n) {
        let num = 0;
        // 解析数字部分，可能有多位数字
        while (i < n && !isNaN(compressed[i])) {
            num = num * 10 + parseInt(compressed[i], 10);
            i++;
        }
        // 当前字符是要重复的字符
        if (i < n) {
            let ch = compressed[i];
            // 重复添加字符
            for (let j = 0; j < num; j++) {
                expanded.push(ch);
            }
            i++;
        }
    }

    return expanded.join('');
}

function main() {
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    
    // 读取输入
    let compressed1 = input[0].trim();
    let compressed2 = input[1].trim();

    // 解压两个字符串
    let expanded1 = decompress(compressed1);
    let expanded2 = decompress(compressed2);

    // 计算误码数量
    let errorCount = 0;
    let totalLength = expanded1.length; // 根据题目，长度相同

    for (let i = 0; i < totalLength; i++) {
        if (expanded1[i] !== expanded2[i]) {
            errorCount++;
        }
    }

    // 输出结果
    console.log(`${errorCount}/${totalLength}`);
}

main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* decompress(const char* compressed) {
    // 预估解压后字符串的长度
    char* expanded = malloc(1000000 * sizeof(char));
    int index = 0;
    int n = strlen(compressed);
    int i = 0;
    
    while (i < n) {
        int num = 0;
        // 解析数字部分，可能有多位数字
        while (i < n && compressed[i] >= '0' && compressed[i] <= '9') {
            num = num * 10 + (compressed[i] - '0');
            i++;
        }
        // 当前字符是要重复的字符
        if (i < n) {
            char ch = compressed[i];
            // 重复添加字符
            for (int j = 0; j < num; j++) {
                expanded[index++] = ch;
            }
            i++;
        }
    }
    expanded[index] = '\0';
    return expanded;
}

int main() {
    char compressed1[1000000];
    char compressed2[1000000];

    // 读取输入
    scanf("%s", compressed1);
    scanf("%s", compressed2);

    // 解压两个字符串
    char* expanded1 = decompress(compressed1);
    char* expanded2 = decompress(compressed2);

    // 计算误码数量
    int errorCount = 0;
    int totalLength = strlen(expanded1); // 根据题目，长度相同

    for (int i = 0; i < totalLength; i++) {
        if (expanded1[i] != expanded2[i]) {
            errorCount++;
        }
    }

    // 输出结果
    printf("%d/%d\n", errorCount, totalLength);

    // 释放内存
    free(expanded1);
    free(expanded2);

    return 0;
}

九、C++算法源码

#include <iostream>
#include <string>
using namespace std;

string decompress(const string& compressed) {
    string expanded;
    int n = compressed.length();
    int i = 0;

    while (i < n) {
        int num = 0;
        // 解析数字部分，可能有多位数字
        while (i < n && isdigit(compressed[i])) {
            num = num * 10 + (compressed[i] - '0');
            i++;
        }
        // 当前字符是要重复的字符
        if (i < n) {
            char ch = compressed[i];
            // 重复添加字符
            expanded.append(num, ch);
            i++;
        }
    }
    return expanded;
}

int main() {
    string compressed1, compressed2;
    // 读取输入
    cin >> compressed1 >> compressed2;

    // 解压两个字符串
    string expanded1 = decompress(compressed1);
    string expanded2 = decompress(compressed2);

    // 计算误码数量
    int errorCount = 0;
    int totalLength = expanded1.length(); // 根据题目，长度相同

    for (int i = 0; i < totalLength; i++) {
        if (expanded1[i] != expanded2[i]) {
            errorCount++;
        }
    }

    // 输出结果
    cout << errorCount << "/" << totalLength << endl;

    return 0;
}

下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。