20天拿下华为OD笔试之【模拟】2025C-猜数字【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解
可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)
文章目录
相关推荐阅读
- 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
- 【华为OD笔试】2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈,不断更新,限时免费】
- 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
- 【华为OD流程】性格测试选项+注意事项】
题目练习网址:【模拟】2025C-猜数字
题目描述与示例
题目描述
一个人设定一组四码的数字作为谜底,另一方猜。
每猜一个数,出数者就要根据这个数字给出提示,提示以XAYB形式呈现,直到猜中为止。
其中X表示位置正确的数的个数(数字正确且位置正确),而Y表示数字正确而位置不对的数的个数。
例如,当谜底为8123,而猜谜者猜1052时,出题者必须提示0A2B.
例如,当谜底为5637,而猜谜者猜4931时,出题者必须提示1A0B.
当前已知N组猜谜者猜的数字与提示,如果答案确定,请输出答案,不确定则输出NA。
输入描述
第一行输入一个正整数,0 < N < 100.
接下来N行,每一行包含一个猜测的数字与提示结果。
输出描述
输出最后的答案,答案不确定则输出NA。
示例
输入
6
4815 1A1B
5716 0A1B
7842 0A1B
4901 0A0B
8585 3A0B
8555 2A1B
输出
3585
解题思路
正向计算这个问题是比较麻烦的。考虑使用枚举的方式来完成本题。
由于答案由四个数字构成,因此一共要枚举10^4个数字。
另外,对于每一个数字而言,都需要去考虑是否和每一个条件匹配。
由于一共存在N个条件,N的最大值为10^2。
因此总的时间复杂度为O(mn) = O(10^6)。这种枚举的办法不会超时。
将数字类型转化为字符串类型
考虑到,如果我们想要比较两个数字之间的关系,用字符串类型来比较的效率要远远优于用整数类型。
因此我们最好是构建一个将数字类型转化为字符串类型的函数。
由于我们枚举数字的时候,会从0枚举到9999。所以对于位数不足4的数字而言,其字符串形式的高位必须用若干的字符"0"来进行填充。譬如把"15"填充为"0015"。
# 将数字转化为长度为4的字符串的函数
def convert(num):
s = str(num)
# (4-len(s))为需要填充在最前面的"0"的个数
return "0"*(4-len(s)) + s
那么,我们就可以通过以下方式来枚举所有数字并转化为字符串类型了
# 枚举从0到9999的数字num
for num in range(10000):
# 将数字num转化为长度为4的字符串s
s = convert(num)
pass
如果想不到上述方法,也可以使用四重for循环,通过从0到9枚举数字的每一位并拼接到一起,来完成所有数字的枚举。
for a in range(10):
for b in range(10):
for c in range(10):
for d in range(10):
# 字符串格式化写法
s = f"{a}{b}{c}{d}"
# 字符串拼接写法
s = str(a) + str(b) + str(c) + str(d)
pass
不过这种写法就显得嵌套过多了,建议还是使用更加简洁的前一种写法来完成枚举。
另外,对于输入的N个条件,我们也可以直接使用字符串格式进行储存,而不用特意去转化为数字。
这样才方便后续进行字符串之间的比较。
# 输入条件个数
N = int(input())
# 构建conditions数组,储存所有N个条件
conditions = list()
# 循环N次,储存每一个条件
for _ in range(N):
# 将每一个条件以形如 ["4815", "1A1B"] 的字符串二元组的格式
# 储存在数组conditions中
conditions.append(input().split())
枚举数字和条件数字的比较
当我们同时拿到枚举数字s,条件数字g(表示guess),以及对应的比较结果r(表示result)的时候,我们需要判断s和g之间的关系是否符合比较结果r。
首先我们需要明确两种比较的严格定义。这在题目中的描述是比较模糊的,我们只能够通过用例反推。
比较条件8585 3A0B和答案3585,可以看到当g = "8585"时,虽然存在第一个"8"和s = "3585"中的"8"位置不同,但是由于g中存在第二个"8"和s中的这个"8"属于数字正确且位置相同的关系,这个条件中的Y为0而不是1。
这说明,条件A的判定优先级要高于条件B。
如果g中存在某个数字既满足条件A又满足条件B,只会计入条件A(增加X的计数)而不会计入条件B(不会增加Y的计数)。
这个结论也可以从条件8555 2A1B和答案3585得到验证。虽然g = "8555"存在第二个"5"和s中的两个"5"位置不同,但是并没有计入条件B,Y为1而不是2(Y是1是因为g中存在数字"8"和s中的"8"位置不同)
所以,我们在做关于X的判定的时候,可以构建一个哈希集合A_set,来储存所有满足条件A的数字。
检查条件A较容易完成,只需要枚举s和g中所有同一位置的数字,比较它们是否相等即可。
如果相等,则将这个数字本身储存在A_set中,方便后续关于条件B的判定。即
# 检查X是否匹配的函数
def check_X(s, g, X, A_set):
# 对于长度为4的字符串s和g,进行逐位枚举
for i in range(4):
# 如果在同一个位置,两者相等,则X递减1
if s[i] == g[i]:
X -= 1
A_set.add(s[i])
# 退出循环后,如果X恰好降到0,说明X匹配,返回True
return X == 0
在得到A_set之后,我们就可以来判定条件B了。
我们使用一个双重循环枚举g和s中的所有下标组合,当g[i]和s[j]相等,且g[i]并不是一个满足条件A的数时(也就是不位于A_set中),我们找到了一个满足条件B的数。
另外需要特别注意,一旦找到一个符合条件B的数字g[i],要使用break直接退出j的遍历,否则可能会发生重复统计。综上代码为
# 检查Y是否匹配的函数
def check_Y(s, g, Y, A_set):
# 枚举g中的每一位数字
for i in range(4):
# 枚举s中的每一位数字
for j in range(4):
# 如果g[i]和s[j]相等,且g[i]并不是一个满足条件A的数
# 则令Y递减1
if g[i] == s[j] and g[i] not in A_set:
Y -= 1
# 注意此处一定要break
# 否则可能会出现g中的某一位数字被重复计算的情况
# 譬如g = "1012", s = "0102"
# 此处不进行break的话,g中的"0"会被重复计算2次
break
# 退出循环后,如果Y恰好降到0,说明Y匹配,返回True
return Y == 0
对于比较结果r,必然由"XAYB"这样的格式组成。
首先我们要把X和Y提取出来,然后构建一个空的A_set,分别计算传入check_X和check_Y的结果。当这两个函数都返回True时,则整体可以返回True。即
# 检查s和g是否匹配比较结果r的函数
def check(s, g, r):
# 提取出比较结果r中的数字X和Y
X, Y = int(r[0]), int(r[2])
# 构建空的哈希集合A_set,用于挑出所有满足条件A的数字
A_set = set()
# 分别调用check_X和check_Y
# 注意此处两个函数的顺序不能调换,因为条件A的判定优先级优于条件B
# 因为必须先执行check_X才可以更新A_set用于check_Y的判断
return check_X(s, g, X, A_set) and check_Y(s, g, Y, A_set)
构建整体代码框架
前一小节的工作主要围绕单个s和g的比较,但别忘了s和g都是要进行枚举的。
所以整体的代码框架为
# 枚举从0到9999的数字num
for num in range(10000):
# 将数字num转化为长度为4的字符串s
s = convert(num)
# 如果所有的(g, r)二元组,都可以和当前的s匹配
# 则说明此时枚举出来的s是一个正确答案,储存s
if all(check(s, g, r) for g, r in conditions):
ans = s
同时还需要注意到,题目告知如果不确定答案,需要直接输出NA。
不确定答案分为两种情况:
- 一个满足所有条件的数字
s都没找到 - 存在超过
1个的满足所有条件的数字s
对于这两种情况,我们可以分别设置"e1"和"e2"两种标识来判断。
在循环外先初始化ans为"e1",表示一开始没找到任何答案,然后修改更新ans的条件
ans = "e1"
# 枚举从0到9999的数字num
for num in range(10000):
# 将数字num转化为长度为4的字符串s
s = convert(num)
# 如果所有的(g, r)二元组,都可以和当前的s匹配
# 则说明此时枚举出来的s是一个正确答案,储存s
if all(check(s, g, r) for g, r in conditions):
# 如果是第一次找到匹配的数字s,此时ans应该为"e1"
# 修改ans为s
if ans == "e1":
ans = s
如果在更新答案时,发现ans并不是"e1",则说明之前已经找到过至少一个匹配所有条件的数字s,此时需要把ans修改为"e2"。最后,ans无论是"e1"还是"e2",都要输出"NA"。
ans = "e1"
# 枚举从0到9999的数字num
for num in range(10000):
# 将数字num转化为长度为4的字符串s
s = convert(num)
# 如果所有的(g, r)二元组,都可以和当前的s匹配
# 则说明此时枚举出来的s是一个正确答案,储存s
if all(check(s, g, r) for g, r in conditions):
# 如果是第一次找到匹配的数字s,此时ans应该为"e1"
# 修改ans为s
if ans == "e1":
ans = s
# 如果ans并不是"e1",说明之前已经找到过至少一个匹配所有条件的数字s
# 需要把ans修改为"e2",表示存在不止一个答案,并且可以提前退出
else:
ans = "e2"
break
# ans无论是"e1"还是"e2",都要输出"NA"
# 否则输出找到的结果s
print("NA") if ans == "e1" or ans == "e2" else print(ans)
这样就完成了整道题目。
代码
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例!
# 地址:https://www.odalgo.com
# 华为OD机试刷题网站:https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
# 题目:【模拟】2024E/2025C-猜数字
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:模拟
# 代码看不懂的地方,请直接在群上提问
# 将数字转化为长度为4的字符串的函数
def convert(num):
s = str(num)
# (4-len(s))为需要填充在最前面的"0"的个数
return "0"*(4-len(s)) + s
# 检查X是否匹配的函数
def check_X(s, g, X, A_set):
# 对于长度为4的字符串s和g,进行逐位枚举
for i in range(4):
# 如果在同一个位置,两者相等,则X递减1
if s[i] == g[i]:
X -= 1
A_set.add(s[i])
# 退出循环后,如果X恰好降到0,说明X匹配,返回True
return X == 0
# 检查Y是否匹配的函数
def check_Y(s, g, Y, A_set):
# 枚举g中的每一位数字
for i in range(4):
# 枚举s中的每一位数字
for j in range(4):
# 如果g[i]和s[j]相等,且g[i]并不是一个满足条件A的数
# 则令Y递减1
if g[i] == s[j] and g[i] not in A_set:
Y -= 1
# 注意此处一定要break
# 否则可能会出现g中的某一位数字被重复计算的情况
# 譬如g = "1012", s = "0102"
# 此处不进行break的话,g中的"0"会被重复计算2次
break
# 退出循环后,如果Y恰好降到0,说明X匹配,返回True
return Y == 0
# 检查s和g是否匹配比较结果r的函数
def check(s, g, r):
# 提取出比较结果r中的数字X和Y
X, Y = int(r[0]), int(r[2])
# 构建空的哈希集合A_set,用于挑出所有满足条件A的数字
A_set = set()
# 分别调用check_X和check_Y
# 注意此处两个函数的顺序不能调换,因为条件A的判定优先级优于条件B
# 因为必须先执行check_X才可以更新A_set用于check_Y的判断
return check_X(s, g, X, A_set) and check_Y(s, g, Y, A_set)
# 输入条件个数
N = int(input())
# 构建conditions数组,储存所有N个条件
conditions = list()
# 循环N次,储存每一个条件
for _ in range(N):
# 将每一个条件以形如 ["4815", "1A1B"] 的字符串二元组的格式
# 储存在数组conditions中
conditions.append(input().split())
ans = "e1"
# 枚举从0到9999的数字num
for num in range(10000):
# 将数字num转化为长度为4的字符串s
s = convert(num)
# 如果所有的(g, r)二元组,都可以和当前的s匹配
# 则说明此时枚举出来的s是一个正确答案,储存s
if all(check(s, g, r) for g, r in conditions):
# 如果是第一次找到匹配的数字s,此时ans应该为"e1"
# 修改ans为s
if ans == "e1":
ans = s
# 如果ans并不是"e1",说明之前已经找到过至少一个匹配所有条件的数字s
# 需要把ans修改为"e2",表示存在不止一个答案,并且可以提前退出
else:
ans = "e2"
break
# ans无论是"e1"还是"e2",都要输出"NA"
# 否则输出找到的结果s
print("NA") if ans == "e1" or ans == "e2" else print(ans)
Java
import java.util.*;
public class Main {
// 将数字转化为长度为4的字符串的函数
public static String convert(int num) {
return String.format("%04d", num);
}
// 检查X是否匹配的函数
public static boolean check_X(String s, String g, int X, Set<Character> A_set) {
for (int i = 0; i < 4; i++) {
if (s.charAt(i) == g.charAt(i)) {
X -= 1;
A_set.add(s.charAt(i));
}
}
return X == 0;
}
// 检查Y是否匹配的函数
public static boolean check_Y(String s, String g, int Y, Set<Character> A_set) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g.charAt(i) == s.charAt(j) && !A_set.contains(g.charAt(i))) {
Y -= 1;
break; // 避免重复计算
}
}
}
return Y == 0;
}
// 检查s和g是否匹配比较结果r的函数
public static boolean check(String s, String g, String r) {
int X = r.charAt(0) - '0';
int Y = r.charAt(2) - '0';
Set<Character> A_set = new HashSet<>();
return check_X(s, g, X, A_set) && check_Y(s, g, Y, A_set);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
scanner.nextLine(); // 读取换行符
List<String[]> conditions = new ArrayList<>();
// 读取N个条件
for (int i = 0; i < N; i++) {
conditions.add(scanner.nextLine().split(" "));
}
String ans = "e1";
// 枚举从0到9999的所有数字
for (int num = 0; num < 10000; num++) {
String s = convert(num);
boolean valid = true;
// 检查是否满足所有(g, r)条件
for (String[] condition : conditions) {
if (!check(s, condition[0], condition[1])) {
valid = false;
break;
}
}
if (valid) {
if (ans.equals("e1")) {
ans = s;
} else {
ans = "e2";
break; // 存在多个解,提前退出
}
}
}
// 输出结果
System.out.println(ans.equals("e1") || ans.equals("e2") ? "NA" : ans);
scanner.close();
}
}
C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
// 将数字转化为长度为4的字符串
string convert(int num) {
string s = to_string(num);
while (s.length() < 4) {
s = "0" + s; // 补齐前导0
}
return s;
}
// 检查X是否匹配
bool check_X(const string &s, const string &g, int X, unordered_set<char> &A_set) {
for (int i = 0; i < 4; i++) {
if (s[i] == g[i]) {
X--;
A_set.insert(s[i]);
}
}
return X == 0;
}
// 检查Y是否匹配
bool check_Y(const string &s, const string &g, int Y, const unordered_set<char> &A_set) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i] == s[j] && A_set.find(g[i]) == A_set.end()) {
Y--;
break; // 避免重复计算
}
}
}
return Y == 0;
}
// 检查s和g是否匹配比较结果r
bool check(const string &s, const string &g, const string &r) {
int X = r[0] - '0';
int Y = r[2] - '0';
unordered_set<char> A_set;
return check_X(s, g, X, A_set) && check_Y(s, g, Y, A_set);
}
int main() {
int N;
cin >> N;
vector<pair<string, string>> conditions;
// 读取N个条件
for (int i = 0; i < N; i++) {
string g, r;
cin >> g >> r;
conditions.emplace_back(g, r);
}
string ans = "e1";
// 枚举从0到9999的所有数字
for (int num = 0; num < 10000; num++) {
string s = convert(num);
bool valid = true;
// 检查是否满足所有(g, r)条件
for (const auto &condition : conditions) {
if (!check(s, condition.first, condition.second)) {
valid = false;
break;
}
}
if (valid) {
if (ans == "e1") {
ans = s;
} else {
ans = "e2";
break; // 存在多个解,提前退出
}
}
}
// 输出结果
cout << ((ans == "e1" || ans == "e2") ? "NA" : ans) << endl;
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM 10000
#define MAX_LEN 5 // 4位数字加上终止符 '\0'
// 将数字转化为长度为4的字符串
void convert(int num, char s[MAX_LEN]) {
sprintf(s, "%04d", num); // 使用sprintf补齐前导0
}
// 检查X是否匹配
int check_X(const char *s, const char *g, int X, int A_set[10]) {
for (int i = 0; i < 4; i++) {
if (s[i] == g[i]) {
X--;
A_set[s[i] - '0'] = 1; // 记录满足条件A的数字
}
}
return X == 0;
}
// 检查Y是否匹配
int check_Y(const char *s, const char *g, int Y, int A_set[10]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i] == s[j] && A_set[g[i] - '0'] == 0) {
Y--;
break; // 避免重复计算
}
}
}
return Y == 0;
}
// 检查s和g是否匹配比较结果r
int check(const char *s, const char *g, const char *r) {
int X = r[0] - '0';
int Y = r[2] - '0';
int A_set[10] = {0}; // 记录哪些数字已经在A_set中
return check_X(s, g, X, A_set) && check_Y(s, g, Y, A_set);
}
int main() {
int N;
scanf("%d", &N);
char conditions[N][2][MAX_LEN]; // 存储N个条件,每个条件包含两个字符串
// 读取N个条件
for (int i = 0; i < N; i++) {
scanf("%s %s", conditions[i][0], conditions[i][1]);
}
char ans[MAX_LEN] = "e1";
char s[MAX_LEN];
// 枚举从0到9999的所有数字
for (int num = 0; num < MAX_NUM; num++) {
convert(num, s);
int valid = 1;
// 检查是否满足所有(g, r)条件
for (int i = 0; i < N; i++) {
if (!check(s, conditions[i][0], conditions[i][1])) {
valid = 0;
break;
}
}
if (valid) {
if (strcmp(ans, "e1") == 0) {
strcpy(ans, s);
} else {
strcpy(ans, "e2");
break; // 存在多个解,提前退出
}
}
}
// 输出结果
if (strcmp(ans, "e1") == 0 || strcmp(ans, "e2") == 0) {
printf("NA\n");
} else {
printf("%s\n", ans);
}
return 0;
}
Node JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 将数字转换为4位长度的字符串,补齐前导0
function convert(num) {
return num.toString().padStart(4, '0');
}
// 检查X是否匹配
function check_X(s, g, X, A_set) {
for (let i = 0; i < 4; i++) {
if (s[i] === g[i]) {
X -= 1;
A_set.add(s[i]);
}
}
return X === 0;
}
// 检查Y是否匹配
function check_Y(s, g, Y, A_set) {
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
if (g[i] === s[j] && !A_set.has(g[i])) {
Y -= 1;
break; // 避免重复计算
}
}
}
return Y === 0;
}
// 检查s和g是否匹配比较结果r
function check(s, g, r) {
let X = parseInt(r[0]);
let Y = parseInt(r[2]);
let A_set = new Set();
return check_X(s, g, X, A_set) && check_Y(s, g, Y, A_set);
}
// 处理输入
let inputLines = [];
rl.on('line', (line) => {
inputLines.push(line);
}).on('close', () => {
let N = parseInt(inputLines[0]); // 读取条件个数
let conditions = inputLines.slice(1).map(line => line.split(' '));
let ans = "e1";
// 枚举从0到9999的所有数字
for (let num = 0; num < 10000; num++) {
let s = convert(num);
let valid = conditions.every(([g, r]) => check(s, g, r));
if (valid) {
if (ans === "e1") {
ans = s;
} else {
ans = "e2";
break; // 存在多个解,提前退出
}
}
}
// 输出结果
console.log(ans === "e1" || ans === "e2" ? "NA" : ans);
});
Go
package main
import (
"fmt"
"strconv"
)
// 将数字转换为4位长度的字符串,补齐前导0
func convert(num int) string {
return fmt.Sprintf("%04d", num)
}
// 检查X是否匹配
func check_X(s, g string, X int, A_set map[rune]bool) bool {
for i := 0; i < 4; i++ {
if s[i] == g[i] {
X--
A_set[rune(s[i])] = true
}
}
return X == 0
}
// 检查Y是否匹配
func check_Y(s, g string, Y int, A_set map[rune]bool) bool {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
if g[i] == s[j] && !A_set[rune(g[i])] {
Y--
break // 避免重复计算
}
}
}
return Y == 0
}
// 检查s和g是否匹配比较结果r
func check(s, g, r string) bool {
X, _ := strconv.Atoi(string(r[0]))
Y, _ := strconv.Atoi(string(r[2]))
A_set := make(map[rune]bool)
return check_X(s, g, X, A_set) && check_Y(s, g, Y, A_set)
}
func main() {
var N int
fmt.Scan(&N)
conditions := make([][2]string, N)
// 读取N个条件
for i := 0; i < N; i++ {
fmt.Scan(&conditions[i][0], &conditions[i][1])
}
ans := "e1"
// 枚举从0到9999的所有数字
for num := 0; num < 10000; num++ {
s := convert(num)
valid := true
// 检查是否满足所有(g, r)条件
for _, condition := range conditions {
if !check(s, condition[0], condition[1]) {
valid = false
break
}
}
if valid {
if ans == "e1" {
ans = s
} else {
ans = "e2"
break // 存在多个解,提前退出
}
}
}
// 输出结果
if ans == "e1" || ans == "e2" {
fmt.Println("NA")
} else {
fmt.Println(ans)
}
}
时空复杂度
时间复杂度:O(mn)。双重循环所需时间复杂度,其中需要枚举的总数字个数m为10000,条件个数n的最大值为100。
空间复杂度:O(1)。除了输入的序列,仅需若干常数变量维护遍历过程,哈希集合的开销也为常数空间。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务1000+同学成功上岸!
-
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
90+天陪伴式学习,100+直播课时,300+动画图解视频,500+LeetCode经典题,500+华为OD真题/大厂真题,还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接OD真题汇总(持续更新)
-
绿色聊天软件戳
od1441或了解更多
更多推荐
所有评论(0)