当前位置：首页 > article >正文

【华为OD-E卷 - 猜数字 100分（python、java、c++、js、c）】

article 2025/1/15 11:15:48

【华为OD-E卷 - 猜数字 100分（python、java、c++、js、c）】

题目

一个人设定一组四码的数字作为谜底，另一方猜。
每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。
其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。
例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。
例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。
当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA

输入描述

第一行输入一个正整数，0＜N ＜ 100。

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

输出描述

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

备注

用例

用例一：

输入：

输出：

python解法

解题思路：
目标:

根据用户的多次猜测结果，从所有可能的4位数字答案中推断唯一符合条件的答案。如果没有答案或有多个可能答案，返回"NA"。
关键逻辑:

每次猜测的结果表示为xAyB，其中x是数字和位置都正确的个数（称为A），y是数字正确但位置不正确的个数（称为B）。
遍历所有可能的4位数字组合，逐一验证是否符合所有猜测的结果条件。
主要功能模块:

getGuessResult: 计算某次猜测与答案的xAyB结果。
isValid: 验证某个答案是否满足所有的猜测结果。
generatePossibleAnswers: 生成所有可能的4位数字组合。
findAnswer: 在所有可能答案中找到唯一符合条件的答案。
实现细节:

使用回溯法生成所有可能的4位数字组合。
遍历所有组合，调用isValid验证是否符合所有猜测。
如果仅有一个符合条件的答案，返回该答案；否则返回"NA"

# 计算某次猜测的结果（xAyB格式）
def getGuessResult(guess, answer):
    countA = 0  # 记录A的数量（数字和位置都正确）
    countB = 0  # 记录B的数量（数字正确但位置不正确）
    answer_arr = [0] * 10  # 记录答案中每个数字的出现次数
    guess_arr = [0] * 10  # 记录猜测中每个数字的出现次数

    # 遍历猜测和答案的每一位
    for i in range(4):
        if guess[i] == answer[i]:
            # 数字和位置都正确，增加A计数
            countA += 1
        else:
            # 数字位置不正确，记录出现次数
            guess_arr[int(guess[i])] += 1
            answer_arr[int(answer[i])] += 1

    # 计算B的数量：取猜测和答案中每个数字的最小出现次数
    for i in range(10):
        countB += min(guess_arr[i], answer_arr[i])

    # 返回结果格式如 "xAyB"
    return f"{countA}A{countB}B"

# 验证某个答案是否满足所有的猜测结果
def isValid(answer, infos):
    for guess, result in infos:
        # 如果当前答案和某次猜测的结果不匹配，答案无效
        if getGuessResult(guess, answer) != result:
            return False
    return True

# 生成所有可能的4位数字组合
def generatePossibleAnswers():
    answers = []  # 存储所有可能的答案

    # 使用回溯法生成数字组合
    def backtrack(path):
        if len(path) == 4:
            # 如果路径长度为4，添加为一个可能答案
            answers.append("".join(path))
            return
        for i in range(10):  # 每次选择0-9中的一个数字
            backtrack(path + [str(i)])

    backtrack([])  # 从空路径开始回溯
    return answers

# 找到唯一符合条件的答案
def findAnswer(infos):
    # 生成所有可能的4位数字组合
    possible_answers = generatePossibleAnswers()

    # 筛选满足所有猜测结果的答案
    valid_answers = [ans for ans in possible_answers if isValid(ans, infos)]

    # 如果只有一个符合条件的答案，返回该答案；否则返回"NA"
    if len(valid_answers) == 1:
        return valid_answers[0]
    else:
        return "NA"

# 主程序入口
n = int(input())  # 读取猜测的次数
infos = [input().split() for _ in range(n)]  # 读取每次猜测及其结果
print(findAnswer(infos))  # 输出唯一符合条件的答案或"NA"

java解法

解题思路
目标:

找出唯一的4位数字密码secret，满足所有用户给出的线索clues。
每条线索由一个猜测和相应的提示（格式为xAyB）组成：
xA: 有x个数字与密码的数字和位置都正确。
yB: 有y个数字与密码的数字正确但位置不正确。
基本逻辑:

枚举所有可能的4位数字密码（0000到9999，共10000个）。
对每个密码，验证它是否满足所有的线索。
如果仅有一个密码满足所有线索，返回该密码；如果没有或有多个符合的密码，返回"NA"。
关键功能模块:

findSecret:
枚举所有可能的密码，验证每个密码是否满足所有线索。
如果仅有一个候选密码，返回该密码；否则返回"NA"。
isMatch:
验证某个密码是否满足所有的线索。
对每条线索，调用generateHint生成实际提示，与预期提示比较。
generateHint:
根据猜测和密码，计算提示值xAyB。
代码实现:

使用两层循环：
外层循环枚举所有可能密码。
内层循环验证密码是否满足每条线索

import java.util.*;

public class Main {
    // 存储用户给出的线索，每个线索由猜测和提示组成
    static String[][] clues;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入线索的数量
        int n = scanner.nextInt();
        clues = new String[n][2];
        // 读取每条线索（猜测和提示）
        for (int i = 0; i < n; i++) {
            clues[i][0] = scanner.next(); // 读取猜测
            clues[i][1] = scanner.next(); // 读取提示
        }

        // 输出唯一符合条件的密码或"NA"
        System.out.println(findSecret());
    }

    // 找到唯一符合线索的密码
    public static String findSecret() {
        List<String> candidates = new ArrayList<>(); // 存储符合条件的候选密码

        // 枚举所有可能的4位数字密码
        for (int i = 0; i < 10000; i++) {
            // 格式化成4位字符串（如 1 -> 0001）
            String secret = String.format("%04d", i);
            // 验证当前密码是否满足所有线索
            if (isMatch(secret)) {
                candidates.add(secret); // 如果满足，加入候选列表
            }
        }

        // 如果仅有一个候选密码，返回该密码；否则返回"NA"
        if (candidates.size() == 1) {
            return candidates.get(0);
        } else {
            return "NA";
        }
    }

    // 验证某个密码是否满足所有线索
    public static boolean isMatch(String secret) {
        // 遍历所有线索
        for (String[] clue : clues) {
            String guess = clue[0];          // 当前线索的猜测
            String expectedHint = clue[1];  // 当前线索的预期提示
            String actualHint = generateHint(guess, secret); // 根据当前密码生成实际提示

            // 如果实际提示与预期提示不一致，返回false
            if (!expectedHint.equals(actualHint)) {
                return false;
            }
        }
        // 如果所有线索均满足，返回true
        return true;
    }

    // 根据猜测和密码，生成提示（格式为xAyB）
    public static String generateHint(String guess, String secret) {
        int correctPosition = 0; // 记录数字和位置都正确的个数（A）
        int correctNumber = 0;   // 记录数字正确但位置不正确的个数（B）

        int[] guessCount = new int[10]; // 记录猜测中每个数字的出现次数
        int[] secretCount = new int[10]; // 记录密码中每个数字的出现次数

        // 遍历4位数字
        for (int i = 0; i < 4; i++) {
            if (guess.charAt(i) == secret.charAt(i)) {
                // 如果数字和位置都正确，增加A计数
                correctPosition++;
            } else {
                // 否则，记录数字的出现次数
                guessCount[guess.charAt(i) - '0']++;
                secretCount[secret.charAt(i) - '0']++;
            }
        }

        // 计算B值：取猜测和密码中每个数字出现次数的最小值
        for (int i = 0; i < 10; i++) {
            correctNumber += Math.min(guessCount[i], secretCount[i]);
        }

        // 返回提示值（如"1A2B"）
        return correctPosition + "A" + correctNumber + "B";
    }
}

C++解法

解题思路

更新中

C解法

解题思路

更新中

JS解法

解题思路
目标:

找到一个唯一的4位数字组合，满足所有提示hints。
每条提示由一个猜测guess和结果result组成：
result的格式为xAyB，表示：
xA：有x个数字的位置和数值都正确。
yB：有y个数字的数值正确但位置不正确。
优化解法:

使用位操作和递归进行优化：
位操作用于记录每个位置可能的数字，减少枚举范围。
深度优先搜索（DFS）用于生成可能的密码组合并验证其有效性。
主要步骤:

初始化可能性数组:
每个位置的可能数字初始为(1 << 10) - 1（即0-9全部可能）。
根据提示逐步更新可能性数组，排除不符合的数字。
深度优先搜索生成候选密码:
按位置递归生成所有可能的4位数字组合。
对每个组合，验证是否满足所有提示。
验证密码有效性:
对每条提示，计算猜测和密码的xAyB值，并与提示结果对比。
关键逻辑:

位操作:
使用poss数组记录每个位置可能的数字集合。
通过按位与和按位取反，动态更新可能的数字集合。
DFS递归:
遍历可能的数字集合，逐个尝试生成密码，并进行验证。

const rl = require('readline').createInterface({ input: process.stdin, output: process.stdout });
const io = [];
rl.on('line', ln => io.push(ln)).on('close', main);

function main() {
    const [n, ...data] = io; // 读取输入的提示数量和提示内容
    console.log(solve(data.map(x => x.split(' ')))); // 解析提示并求解
}

function solve(hints) {
    // 初始化每个位置可能的数字集合，初始为0-9全部可能
    let poss = Array(4).fill((1 << 10) - 1);

    // 根据提示更新可能性数组
    for (let [g, r] of hints) {
        let [a, b] = r.split('A'); // 提取结果的xA和yB
        b = b[0]; // 只需要y的值

        if (a == '0') { // 如果提示xA为0
            for (let i = 0; i < 4; i++) {
                if (b == '0') {
                    // 如果yB为0，数字在该位置不可能出现
                    poss[i] &= ~(1 << +g[i]);
                } else {
                    // 否则，该数字可能出现在其他位置，但不能同时占多个位置
                    poss[i] &= ~(1 << +g[i]) | (1 << 10);
                }
            }
        }
    }

    // 用于存储符合条件的候选密码
    let res = [];
    // 开始DFS搜索符合条件的密码
    dfs(0, [], poss, hints, res);

    // 如果只有一个符合条件的密码，返回该密码；否则返回"NA"
    return res.length === 1 ? res[0].join('') : 'NA';
}

// 深度优先搜索，生成密码组合并验证其有效性
function dfs(idx, curr, poss, hints, res) {
    if (idx === 4) { // 如果已生成4位密码
        if (isValid(curr, hints)) res.push([...curr]); // 验证密码是否有效
        return;
    }
    for (let i = 0; i < 10; i++) {
        if (poss[idx] & (1 << i)) { // 检查当前位置是否可能为数字i
            curr.push(i); // 将数字i加入当前密码组合
            dfs(idx + 1, curr, poss, hints, res); // 递归处理下一位
            curr.pop(); // 回溯，移除当前数字
        }
    }
}

// 验证当前密码是否满足所有提示
function isValid(guess, hints) {
    for (let [g, r] of hints) {
        let [a, b] = calcAB(guess, g.split('').map(Number)); // 计算实际的xA和yB
        if (a != r[0] || b != r[2]) return false; // 如果不匹配，返回false
    }
    return true; // 所有提示均匹配，返回true
}

// 计算猜测和答案的xA和yB值
function calcAB(ans, guess) {
    let a = 0, b = 0;
    let m1 = Array(10).fill(0), m2 = Array(10).fill(0);

    // 遍历4位数字
    for (let i = 0; i < 4; i++) {
        if (ans[i] === guess[i]) {
            a++; // 数字和位置都正确，增加xA
        } else {
            m1[ans[i]]++; // 记录答案中的数字
            m2[guess[i]]++; // 记录猜测中的数字
        }
    }

    // 计算yB：取每个数字出现次数的最小值
    for (let i = 0; i < 10; i++) b += Math.min(m1[i], m2[i]);

    return [a, b]; // 返回xA和yB
}