可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练(备注【CSDN】否则不通过)

相关推荐阅读

题目练习网址:【模拟】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循环,通过从09枚举数字的每一位并拼接到一起,来完成所有数字的枚举。

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)的时候,我们需要判断sg之间的关系是否符合比较结果r

首先我们需要明确两种比较的严格定义。这在题目中的描述是比较模糊的,我们只能够通过用例反推。

比较条件8585 3A0B和答案3585,可以看到当g = "8585"时,虽然存在第一个"8"s = "3585"中的"8"位置不同,但是由于g中存在第二个"8"s中的这个"8"属于数字正确且位置相同的关系,这个条件中的Y0而不是1

这说明,条件A的判定优先级要高于条件B

如果g中存在某个数字既满足条件A又满足条件B,只会计入条件A(增加X的计数)而不会计入条件B(不会增加Y的计数)。

这个结论也可以从条件8555 2A1B和答案3585得到验证。虽然g = "8555"存在第二个"5"s中的两个"5"位置不同,但是并没有计入条件BY1而不是2Y1是因为g中存在数字"8"s中的"8"位置不同)

所以,我们在做关于X的判定的时候,可以构建一个哈希集合A_set,来储存所有满足条件A的数字。

检查条件A较容易完成,只需要枚举sg中所有同一位置的数字,比较它们是否相等即可。

如果相等,则将这个数字本身储存在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了。

我们使用一个双重循环枚举gs中的所有下标组合,当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"这样的格式组成。

首先我们要把XY提取出来,然后构建一个空的A_set,分别计算传入check_Xcheck_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)

构建整体代码框架

前一小节的工作主要围绕单个sg的比较,但别忘了sg都是要进行枚举的。

所以整体的代码框架为

# 枚举从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

不确定答案分为两种情况:

  1. 一个满足所有条件的数字s都没找到
  2. 存在超过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)。双重循环所需时间复杂度,其中需要枚举的总数字个数m10000,条件个数n的最大值为100

空间复杂度:O(1)。除了输入的序列,仅需若干常数变量维护遍历过程,哈希集合的开销也为常数空间。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务1000+同学成功上岸!

  • 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 90+天陪伴式学习,100+直播课时,300+动画图解视频,500+LeetCode经典题,500+华为OD真题/大厂真题,还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1441或了解更多

Logo

Agent 垂直技术社区,欢迎活跃、内容共建。

更多推荐