题号：面试题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种字符
示例：
输入：solution="RGBY",guess="GGRR"输出：[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 3solution：R G G B guess： G B G B 结果： 伪 无 猜 猜
可以观察到某个颜色在两边出现的次数与 猜中 + 伪猜中 有关，以G为例，G在两边各出现2次，在0号位上有一次伪猜中，在2号位上有一次猜中；再以B为例，B在solution中出现1次，在guess中出现2次，只有3号位上有一次猜中，而在1号位上，由于solution中的B数量不足，没有元素与其匹配。
综上，我们可以得到这个规律：对于某一颜色，min（solution，guess）= 猜中 + 伪猜中。
使用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关注我，从零开始的算法小白之路。
