阿里云wordpress建站教程独立网站怎么做
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
一个人设定一组四码的数字作为谜底，另一方猜。
每猜一个数，出题者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。
其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。
例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。
例如，当谜底为5637，而猜谜者猜4931时，出题者必须提示1A0B。
当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。
二、输入描述
第一行输入一个正整数N，0 < N < 100。
接下来N行，每一行包含一个猜测的数字与提示结果。
三、输出描述
输出最后的答案，答案不确定则输出NA。
四、测试用例
测试用例1
1、输入
3
1234 1A2B
5678 0A1B
9012 0A0B
2、输出
NA
3、说明
没有唯一符合所有提示的谜底，因此输出"NA"。
测试用例2
1、输入
2
0000 4A0B
1111 0A0B
2、输出
0000
3、说明
唯一符合所有提示的谜底是0000。
五、解题思路
本题的核心算法是穷举所有可能的四位数字组合（从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。
由于数据范围相对较小，穷举法可以在合理的时间内解决问题。
六、Python算法源码
# 导入必要的模块
import sysdef main():# 读取所有输入并按空白字符分割input = sys.stdin.read().split()index = 0# 读取猜测次数Nn = int(input[index])index += 1# 初始化猜测和提示的列表guesses = []hints = []# 读取每一组猜测和提示for _ in range(n):guesses.append(input[index])hints.append(input[index + 1])index += 2# 查找可能的谜底result = findPossibleAnswer(n, guesses, hints)# 输出结果print(result)def findPossibleAnswer(n, guesses, hints):possibleAnswer = None# 遍历所有可能的四位数字for i in range(10000):# 将数字格式化为四位字符串currentGuess = f"{i:04d}"isValid = True# 验证当前数字是否符合所有提示for j in range(n):# 生成当前猜测与谜底的提示hint = generateHint(currentGuess, guesses[j])# 如果提示不匹配，则当前数字不符合if hint != hints[j]:isValid = Falsebreak# 如果当前数字符合所有提示if isValid:if possibleAnswer is None:possibleAnswer = currentGuesselse:# 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA"# 返回唯一的谜底或"NA"return possibleAnswer if possibleAnswer is not None else "NA"def generateHint(answer, guess):A = 0 # 数字正确且位置正确的个数B = 0 # 数字正确但位置不对的个数# 标记已经匹配的数字answerUsed = [False] * 4guessUsed = [False] * 4# 先计算A值for i in range(4):if answer[i] == guess[i]:A += 1answerUsed[i] = TrueguessUsed[i] = True# 再计算B值for i in range(4):if not guessUsed[i]:for j in range(4):if not answerUsed[j] and guess[i] == answer[j]:B += 1answerUsed[j] = Truebreak# 返回提示字符串return f"{A}A{B}B"# 调用主函数
if __name__ == "__main__":main()七、JavaScript算法源码
// 使用标准输入输出
process.stdin.resume();
process.stdin.setEncoding('utf8');let input = '';// 读取输入数据
process.stdin.on('data', function(chunk) {input += chunk;
});// 输入结束后处理数据
process.stdin.on('end', function() {// 按空白字符分割输入const tokens = input.trim().split(/\s+/);let index = 0;// 读取猜测次数Nconst n = parseInt(tokens[index++], 10);// 初始化猜测和提示的数组const guesses = [];const hints = [];// 读取每一组猜测和提示for(let i = 0; i < n; i++) {guesses.push(tokens[index++]);hints.push(tokens[index++]);}// 查找可能的谜底const result = findPossibleAnswer(n, guesses, hints);// 输出结果console.log(result);
});// 定义查找可能谜底的函数
function findPossibleAnswer(n, guesses, hints) {let possibleAnswer = null;// 遍历所有可能的四位数字for(let i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串const currentGuess = i.toString().padStart(4, '0');let isValid = true;// 验证当前数字是否符合所有提示for(let j = 0; j < n; j++) {// 生成当前猜测与谜底的提示const hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(hint !== hints[j]) {isValid = false;break;}}// 如果当前数字符合所有提示if(isValid) {if(possibleAnswer === null) {possibleAnswer = currentGuess;} else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA";}}}// 返回唯一的谜底或"NA"return possibleAnswer !== null ? possibleAnswer : "NA";
}// 定义生成提示的函数
function generateHint(answer, guess) {let A = 0; // 数字正确且位置正确的个数let B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字const answerUsed = [false, false, false, false];const guessUsed = [false, false, false, false];// 先计算A值for(let i = 0; i < 4; i++) {if(answer[i] === guess[i]) {A += 1;answerUsed[i] = true;guessUsed[i] = true;}}// 再计算B值for(let i = 0; i < 4; i++) {if(!guessUsed[i]) {for(let j = 0; j < 4; j++) {if(!answerUsed[j] && guess[i] === answer[j]) {B += 1;answerUsed[j] = true;break;}}}}// 返回提示字符串return `${A}A${B}B`;
}八、C算法源码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义最大可能的谜底数量
#define MAX_POSSIBLE 10000// 函数声明
char* findPossibleAnswer(int n, char guesses[][5], char hints[][5]);
char* generateHint(char* answer, char* guess);int main(){int n;// 读取猜测次数Nscanf("%d", &n);// 动态分配猜测和提示的数组char (*guesses)[5] = malloc(n * sizeof(*guesses));char (*hints)[5] = malloc(n * sizeof(*hints));// 读取每一组猜测和提示for(int i = 0; i < n; i++) {scanf("%s %s", guesses[i], hints[i]);}// 查找可能的谜底char* result = findPossibleAnswer(n, guesses, hints);// 输出结果printf("%s\n", result);// 释放动态分配的内存free(guesses);free(hints);free(result);return 0;
}// 定义查找可能谜底的函数
char* findPossibleAnswer(int n, char guesses[][5], char hints[][5]) {char* possibleAnswer = NULL;// 遍历所有可能的四位数字for(int i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串char currentGuess[5];sprintf(currentGuess, "%04d", i);int isValid = 1;// 验证当前数字是否符合所有提示for(int j = 0; j < n; j++) {// 生成当前猜测与谜底的提示char* hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(strcmp(hint, hints[j]) != 0) {isValid = 0;free(hint);break;}free(hint);}// 如果当前数字符合所有提示if(isValid) {if(possibleAnswer == NULL) {possibleAnswer = malloc(5 * sizeof(char));strcpy(possibleAnswer, currentGuess);}else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"free(possibleAnswer);return "NA";}}}// 返回唯一的谜底或"NA"if(possibleAnswer != NULL) {return possibleAnswer;}else {// 分配内存存储"NA"char* na = malloc(3 * sizeof(char));strcpy(na, "NA");return na;}
}// 定义生成提示的函数
char* generateHint(char* answer, char* guess){int A = 0; // 数字正确且位置正确的个数int B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字int answerUsed[4] = {0, 0, 0, 0};int guessUsed[4] = {0, 0, 0, 0};// 先计算A值for(int i = 0; i < 4; i++) {if(answer[i] == guess[i]) {A += 1;answerUsed[i] = 1;guessUsed[i] = 1;}}// 再计算B值for(int i = 0; i < 4; i++) {if(!guessUsed[i]) {for(int j = 0; j < 4; j++) {if(!answerUsed[j] && guess[i] == answer[j]) {B += 1;answerUsed[j] = 1;break;}}}}// 分配内存存储提示字符串char* hintStr = malloc(5 * sizeof(char));sprintf(hintStr, "%dA%dB", A, B);return hintStr;
}九、C++算法源码
#include <bits/stdc++.h>
using namespace std;// 函数声明
string findPossibleAnswer(int n, vector<string> guesses, vector<string> hints);
string generateHint(string answer, string guess);int main(){int n;// 读取猜测次数Ncin >> n;// 初始化猜测和提示的向量vector<string> guesses(n);vector<string> hints(n);// 读取每一组猜测和提示for(int i = 0; i < n; i++) {cin >> guesses[i] >> hints[i];}// 查找可能的谜底string result = findPossibleAnswer(n, guesses, hints);// 输出结果cout << result << "\n";return 0;
}// 定义查找可能谜底的函数
string findPossibleAnswer(int n, vector<string> guesses, vector<string> hints){string possibleAnswer = "";bool multiple = false;// 遍历所有可能的四位数字for(int i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串string currentGuess = to_string(i);while(currentGuess.length() < 4) currentGuess = "0" + currentGuess;bool isValid = true;// 验证当前数字是否符合所有提示for(int j = 0; j < n; j++) {// 生成当前猜测与谜底的提示string hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(hint != hints[j]) {isValid = false;break;}}// 如果当前数字符合所有提示if(isValid){if(possibleAnswer.empty()) {possibleAnswer = currentGuess;}else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA";}}}// 返回唯一的谜底或"NA"return possibleAnswer.empty() ? "NA" : possibleAnswer;
}// 定义生成提示的函数
string generateHint(string answer, string guess){int A = 0; // 数字正确且位置正确的个数int B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字vector<bool> answerUsed(4, false);vector<bool> guessUsed(4, false);// 先计算A值for(int i = 0; i < 4; i++) {if(answer[i] == guess[i]) {A += 1;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[i] == answer[j]) {B += 1;answerUsed[j] = true;break;}}}}// 返回提示字符串return to_string(A) + "A" + to_string(B) + "B";
}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
