题号面试题16.15 珠玑妙算题目内容珠玑妙算游戏the game of master mind的玩法如下。计算机有4个槽每个槽放一个球颜色可能是红色R、黄色Y、绿色G或蓝色B。例如计算机可能有RGGB 4种槽1为红色槽2、3为绿色槽4为蓝色。作为用户你试图猜出颜色组合。打个比方你可能会猜YRGB。要是猜对某个槽的颜色则算一次“猜中”要是只猜对颜色但槽位猜错了则算一次“伪猜中”。注意“猜中”不能算入“伪猜中”。给定一种颜色组合solution和一个猜测guess编写一个方法返回猜中和伪猜中的次数answer其中answer[0]为猜中的次数answer[1]为伪猜中的次数。注len(solution) len(guess) 4solution和guess仅包含R,G,B,Y这4种字符示例输入solutionRGBY,guessGGRR输出[1,1]解释猜中1次伪猜中1次。解题过程与思路这道题可以拆分为两个子问题一个是计算猜中另一个是计算伪猜中。对于猜中问题采用很简单的同步遍历法即可此处不再赘述。对于伪猜中问题其核心是如何处理 “猜中”不能算入“伪猜中” 这一条件此处我采用的思路是把原来的字符串转化为列表先依次遍历求解猜中问题对于已经猜中的字符则从列表中删除这样就可以避免重复计数。使用python编写代码如下def master_mind(solution: str, guess: str) - List[int]: # 将原始字符串转化为列表 l_solution list(solution) l_guess list(guess) # 初始化答案 answer [0, 0] # 初始化列表长度与计数器 num len(l_guess) i 0 while i num: # 同步遍历 if l_guess[i] l_solution[i]: # 猜中 answer[0] 1 # 猜中则答案1 # 删除已猜中的元素 l_solution.pop(i) l_guess.pop(i) # 更新列表长度防止索引越界 num - 1 # i保持原位 i - 1 i 1 # 更新索引 # 遍历剩余的元素判断是否伪猜中因为此时已经排除了猜中的元素所以只需要判断是否在solution中存在即可 for item in l_guess: if item in l_solution: # 判断是否伪猜中 answer[1] 1 l_solution.remove(item) # 删除元素防止重复计算 return answer优化可以看到上面的算法使用了较为复杂的索引更新理解难度较大并且容易导致索引越界或者跳过元素。因此我们采用更优雅的方式解决伪猜中问题这个方法由ai提供以solution R G G B,guess G R G B为例其元素有如下的对应关系位置0 1 2 3solutionR G G B guess G B G B 结果 伪 无 猜 猜可以观察到某个颜色在两边出现的次数与 猜中 伪猜中 有关以G为例G在两边各出现2次在0号位上有一次伪猜中在2号位上有一次猜中再以B为例B在solution中出现1次在guess中出现2次只有3号位上有一次猜中而在1号位上由于solution中的B数量不足没有元素与其匹配。综上我们可以得到这个规律对于某一颜色minsolutionguess 猜中 伪猜中。使用python编写代码如下def master_mind_improved(solution: str, guess: str) - List[int]: answer [0, 0] answer[0] sum(s g for s, g in zip(solution, guess)) # 猜中的次数 # 计算总匹配数 count_s Counter(solution) count_g Counter(guess) total sum(min(count_s[c], count_g[c]) for c in count_g) # 减去猜中的次数得到伪猜中的次数 answer[1] total - answer[0] return answer关注我从零开始的算法小白之路。