哪个网站做h5比较好看,遵义网站建设推广,公众号的文章下载 wordpress,驻马店网站优化华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试真题Python/JS/C/C》。
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
一、题目描述
一个人设定一组四码的数字作为谜底另一方猜。
每猜一个数出题者就要根据这个数字给出提示提示以XAYB形式呈现直到猜中位置。
其中X表示位置正确的数的个数数字正确且位置正确而Y表示数字正确而位置不对的数的个数。
例如当谜底为8123而猜谜者猜1052时出题者必须提示0A2B。
例如当谜底为5637而猜谜者猜4931时出题者必须提示1A0B。
当前已知N组猜谜者猜的数字与提示如果答案确定请输出答案不确定则输出NA。
二、输入描述
第一行输入一个正整数N0 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:# 如果已经有一个符合的谜底则不唯一返回NAreturn NA# 返回唯一的谜底或NAreturn possibleAnswer if possibleAnswer is not None else NAdef 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 {// 如果已经有一个符合的谜底则不唯一返回NAreturn NA;}}}// 返回唯一的谜底或NAreturn 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 {// 如果已经有一个符合的谜底则不唯一返回NAfree(possibleAnswer);return NA;}}}// 返回唯一的谜底或NAif(possibleAnswer ! NULL) {return possibleAnswer;}else {// 分配内存存储NAchar* 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, vectorstring guesses, vectorstring hints);
string generateHint(string answer, string guess);int main(){int n;// 读取猜测次数Ncin n;// 初始化猜测和提示的向量vectorstring guesses(n);vectorstring 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, vectorstring guesses, vectorstring 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 {// 如果已经有一个符合的谜底则不唯一返回NAreturn NA;}}}// 返回唯一的谜底或NAreturn possibleAnswer.empty() ? NA : possibleAnswer;
}// 定义生成提示的函数
string generateHint(string answer, string guess){int A 0; // 数字正确且位置正确的个数int B 0; // 数字正确但位置不对的个数// 标记已经匹配的数字vectorbool answerUsed(4, false);vectorbool 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在线答疑。
