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

华为OD机试 - 猜数字 - 穷举搜索（Java 2024 E卷 100分）

news 来源：原创 2024/9/19 11:58:28

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

一个人设定一组四码的数字作为谜底，另一方猜。

每猜一个数，出题者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。

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

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

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

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

二、输入描述

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

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

三、输出描述

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

四、解题思路

本题的核心算法是穷举所有可能的四位数字组合（从0000到9999），即遍历所有可能的谜底。

对于每一个可能的谜底，逐一检查它是否能满足所有给定的提示。

1、为什么采用穷举搜索？

题目要求我们找出一个四位数的谜底，这意味着谜底的取值范围是从0000到9999，总共只有10000种可能。

对于计算机来说，遍历10000种可能性是一个非常可控的操作，执行时间相对较短。因此，使用穷举搜索可以在合理的时间内完成。

2、具体步骤：

枚举所有可能的谜底
- 谜底是一个四位数，范围从0000到9999，总共有10000种可能性。
- 我们需要遍历所有这些可能性，逐个验证它们是否符合所有提示。
验证每一个可能的谜底
- 对于每一个可能的谜底，我们需要根据所有的提示验证它是否符合条件。
- 提示格式为 XAYB，其中：
- X 表示猜测中有多少个数字在正确的位置上。
- Y 表示猜测中有多少个数字是正确的，但位置不对。
具体验证步骤如下：
- 对于每个提示，计算当前可能谜底与猜测之间的 X 和 Y 值。
- 将计算出的 X 和 Y 与输入的提示进行比较，如果不相等，则该可能的谜底无效。

3、复杂度分析

总共有10000个可能的四位数谜底。

对于每个可能的谜底，需要验证它是否符合N个提示。时间复杂度为 O(10000×N)，在最坏情况下，N为100。

由于数据范围相对较小，穷举法可以在合理的时间内解决问题。

六、Java算法源码

public class OdTest01 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 读取NString[] guesses = new String[n];String[] hints = new String[n];// 读取猜测和提示for (int i = 0; i < n; i++) {guesses[i] = scanner.next();hints[i] = scanner.next();}String result = findPossibleAnswer(n, guesses, hints);System.out.println(result);}// 检查一个数字是否满足所有提示private static String findPossibleAnswer(int n, String[] guesses, String[] hints) {String possibleAnswer = null;// 遍历所有可能的谜底for (int i = 0; i <= 9999; i++) {String currentGuess = String.format("%04d", i);boolean isValid = true;// 对于每个猜测，验证是否符合提示for (int j = 0; j < n; j++) {String hint = generateHint(currentGuess, guesses[j]);if (!hint.equals(hints[j])) {isValid = false;break;}}// 如果找到一个符合所有提示的谜底if (isValid) {if (possibleAnswer == null) {possibleAnswer = currentGuess;} else {// 如果已经有一个符合的谜底，则不确定谜底return "NA";}}}return possibleAnswer == null ? "NA" : possibleAnswer;}// 根据当前猜测与实际谜底生成提示private static String generateHint(String answer, String guess) {int A = 0; // 数字正确且位置正确的个数int B = 0; // 数字正确但位置不正确的个数boolean[] answerUsed = new boolean[4];boolean[] guessUsed = new boolean[4];// 先计算A值for (int i = 0; i < 4; i++) {if (answer.charAt(i) == guess.charAt(i)) {A++;answerUsed[i] = true;guessUsed[i] = true;}}// 再计算B值for (int i = 0; i < 4; i++) {if (!guessUsed[i]) {for (int j = 0; j < 4; j++) {if (!answerUsed[j] && guess.charAt(i) == answer.charAt(j)) {B++;answerUsed[j] = true;break;}}}}return A + "A" + B + "B";}
}