【最新华为OD机试E卷】字母组合(200分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队｜大厂实习经历｜多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

🎀关于华为OD

✨华为OD的概念华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
⌚️华为 OD 应聘流程
- 第一步：投递简历
  - 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。
- 第二步：机试
  - 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。
- 第三步：技术面
  - 2 轮技术面试。
- 第四步：HR 与主管面试
- 第五步：录用，发 offer

alt

🍓OJ题目截图

alt

🎵 字母组合

问题描述

给定一个数字到字母的映射关系和一个屏蔽字符串，要求根据输入的数字字符串生成所有可能的字母组合，但需要排除包含屏蔽字符串中所有字母的组合。

数字到字母的映射关系如下：

0 对应 "a", "b", "c"
1 对应 "d", "e", "f"
2 对应 "g", "h", "i"
3 对应 "j", "k", "l"
4 对应 "m", "n", "o"
5 对应 "p", "q", "r"
6 对应 "s", "t"
7 对应 "u", "v"
8 对应 "w", "x"
9 对应 "y", "z"

屏蔽字符串中的所有字母不能同时出现在输出的字符串中。例如，如果屏蔽字符串是 "abc"，则输出的字符串中不能同时包含 a、b 和 c，但可以包含其中的一个或两个。

输入格式

输入包含两行：

第一行是一个数字字符串，长度大于 0 且小于等于 5，其中的数字不允许重复。
第二行是屏蔽字符串，长度小于数字字符串的长度，其中的字符不会重复。

输出格式

输出所有可能的字符串组合，每个字符串后面都要加上逗号，包括最后一个。

样例输入

78
ux

样例输出

uw,vw,vx,

样例解释

数字字符串 "78" 可以生成以下组合：uw、ux、vw、vx。由于 "ux" 是屏蔽字符串，所以 "ux" 被排除，最终输出 uw、vw、vx。

数据范围

数字字符串长度：1 ≤ 长度 ≤ 5
屏蔽字符串长度 < 数字字符串长度

题解

这道题目的核心在于如何高效地生成所有可能的组合，并在生成过程中排除不符合要求的组合。

以下是解题思路：

首先，创建一个数字到字母的映射字典，方便快速查找每个数字对应的字母。
使用递归或回溯的方法生成所有可能的组合。在生成过程中，对于每个数字，我们尝试它对应的所有字母。
在生成组合的同时，需要检查当前组合是否包含了屏蔽字符串中的所有字母。可以使用一个计数器来记录已匹配的屏蔽字符数量。
如果在某个组合中，屏蔽字符的匹配数量等于屏蔽字符串的长度，则说明这个组合包含了所有屏蔽字符，应该被排除。
当生成的组合长度等于数字字符串的长度时，如果该组合有效（不包含所有屏蔽字符），则将其添加到结果列表中。
最后，按要求格式化输出结果。

这种方法的时间复杂度为 $O(3^n)$ ，其中 $n$ 是数字字符串的长度。这是因为在最坏情况下（每个数字对应 3 个字母），我们需要生成 $3^n$ 个组合。

参考代码

以下是五种语言的参考代码实现：

Python

# 定义数字到字母的映射
digit_to_letters = {
    '0': 'abc', '1': 'def', '2': 'ghi', '3': 'jkl', '4': 'mno',
    '5': 'pqr', '6': 'st', '7': 'uv', '8': 'wx', '9': 'yz'
}

def generate_combinations(digits, block, index, current, result, block_count):
    # 如果当前组合长度等于数字字符串长度，检查是否有效
    if len(current) == len(digits):
        if block_count < len(block):
            result.append(current)
        return
    
    # 获取当前数字对应的字母
    letters = digit_to_letters[digits[index]]
    for letter in letters:
        # 检查当前字母是否在屏蔽字符串中
        new_block_count = block_count + (letter in block)
        # 如果屏蔽字符数量未超过限制，继续递归
        if new_block_count < len(block):
            generate_combinations(digits, block, index + 1, current + letter, result, new_block_count)

# 主函数
def main():
    # 读取输入
    digits = input().strip()
    block = input().strip()
    
    # 生成组合
    result = []
    generate_combinations(digits, block, 0, "", result, 0)
    
    # 格式化输出
    print(','.join(result) + ',')

if __name__ == "__main__":
    main()

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

// 定义数字到字母的映射
const char *digitToLetters[] = {
    "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
};

// 生成组合的递归函数
void generateCombinations(const char *digits, const char *block, int index, 
                          char *current, int currentLen, char **result, int *resultSize, int blockCount) {
    // 如果当前组合长度等于数字字符串长度，检查是否有效
    if (index == strlen(digits)) {
        if (blockCount < strlen(block)) {
            current[currentLen] = '\0';  // 结束当前字符串
            result[*resultSize] = (char *)malloc((currentLen + 1) * sizeof(char));
            strcpy(result[*resultSize], current);
            (*resultSize)++;
        }
        return;
    }
    
    // 获取当前数字对应的字母
    const char *letters = digitToLetters[digits[index] - '0'];
    for (int i = 0; letters[i] != '\0'; ++i) {
        char letter = letters[i];
        // 检查当前字母是否在屏蔽字符串中
        int newBlockCount = blockCount + (strchr(block, letter) != NULL);
        // 如果屏蔽字符数量未超过限制，继续递归
        if (newBlockCount < strlen(block)) {
            current[currentLen] = letter;  // 将当前字母加入到组合中

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

最新华为OD机试-E+D卷文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测