【最新华为OD机试E卷】猜数字(100分)

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

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

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

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

最新华为OD机试E卷目录，全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试目录: https://www.nowcoder.com/share/jump/3022116661724989756887

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

3️⃣ 猜数字

问题描述

一个人设定一组四码的数字作为谜底，另一方猜。每猜一个数，出数者就要根据这个数字给出提示，提示以 XAYB 形式呈现，直到猜中位置。

其中 X 表示位置正确的数的个数（数字正确且位置正确），而 Y 表示数字正确而位置不对的数的个数。

例如，当谜底为 8123，而猜谜者猜 1052 时，出题者必须提示 0A2B。

例如，当谜底为 5637，而猜谜者猜 4931 时，出题者必须提示 1A0B。

当前已知 组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出 NA。

输入格式

第一行输入一个正整数 ，。

接下来 行，每一行包含一个猜测的数字与提示结果。

输出格式

输出最后的答案，答案不确定则输出 NA。

样例输入

6
4815 1A1B
5716 0A1B
7842 0A1B
4901 0A0B
8585 3A0B
8555 2A1B

样例输出

3585

样例解释

无

数据范围

题解

给定了一系列猜测和相应的提示，需要找出唯一符合所有条件的答案。

一个直观的解法是暴力枚举所有可能的谜底，即 0000~9999，然后用每一个可能的谜底去验证输入的所有猜测。如果一个数字能够满足所有的猜测和提示，那么它就是可能的答案。

具体步骤如下：

1. 读取输入的猜测和提示。
2. 遍历 0000 到 9999 的所有四位数。
3. 对于每个四位数，检查它是否满足所有的猜测和提示。
4. 如果找到唯一一个满足所有条件的数，输出这个数。
5. 如果没有找到满足条件的数，或者找到多个满足条件的数，输出 "NA"。

这个算法的时间复杂度是 ，其中 是猜测的次数。虽然看起来复杂度较高，但考虑到 的范围（）和四位数的固定范围（0000~9999），实际运行时间是可以接受的。

参考代码

以下是五种语言的实现，都采用了ACM模式，自行处理输入输出：

• Python

def check(guess, answer):
    """检查猜测是否符合提示"""
    a, b = 0, 0
    used_guess = [False] * 4
    used_answer = [False] * 4
    
    # 检查位置和数字都正确的情况
    for i in range(4):
        if guess[i] == answer[i]:
            a += 1
            used_guess[i] = used_answer[i] = True
    
    # 检查数字正确但位置不对的情况
    for i in range(4):
        if not used_guess[i]:
            for j in range(4):
                if not used_answer[j] and guess[i] == answer[j]:
                    b += 1
                    used_answer[j] = True
                    break
    
    return f"{a}A{b}B"

# 读取输入
n = int(input())
guesses = []
for _ in range(n):
    guess, hint = input().split()
    guesses.append((guess, hint))

# 枚举所有可能的答案
possible_answers = []
for num in range(10000):
    answer = f"{num:04d}"
    if all(check(guess, answer) == hint for guess, hint in guesses):
        possible_answers.append(answer)

# 输出结果
if len(possible_answers) == 1:
    print(possible_answers[0])
else:
    print("NA")

• C

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

#define MAX_N 100

char guesses[MAX_N][5];
char hints[MAX_N][5];
int n;

char* check(const char* guess, const char* answer) {
    int a = 0, b = 0;
    bool used_guess[4] = {false};
    bool used_answer[4] = {false};
    
    // 检查位置和数字都正确的情况
    for (int i = 0; i < 4; i++) {
        if (guess[i] == answer[i]) {
            a++;
            used_guess[i] = used_answer[i] = true;
        }
    }
    
    // 检查数字正确但位置不对的情况
    for (int i = 0; i < 4; i++) {
        if (!used_guess[i]) {
            for (int j = 0; j < 4; j++) {
                if (!used_answer[j] && guess[i] == answer[j]) {
                    b++;
                    used_answer[j] = true;
                    break;
                }
            }
        }
    }
    
    static char result[5];
    sprintf(result, "%dA%dB", a, b);
    return result;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s %s", guesses[i], hints[i]);
    }
    
    char possible_answer[5];
    int count = 0;
    char last_answer[5] = "";
    
    for (int num = 0; num < 10000; num++) {
        sprintf(possible_answer, "%04d", num);
        bool valid = true;
        
        for (int i = 0; i < n; i++) {
            if (strcmp(check(guesses[i], possible_answer), hints[i]) != 0) {
                valid = false;
                break;
            }