题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
珠玑妙算游戏（the game of master mind）的玩法如下。
计算机有 4 个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝***）。例如，计算机可能有 RGGB 4 种（槽 1 为红色，槽 2、3 为绿色，槽 4 为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜 YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合 solution 和一个猜测 guess，编写一个方法，返回猜中和伪猜中的次数 answer，其中 answer[0]为猜中的次数，answer[1]为伪猜中的次数。
示例：
- 输入： solution="RGBY",guess="GGRR"
- 输出： [1,1]
- 解释： 猜中 1 次，伪猜中 1 次。
提示：
- len(solution) = len(guess) = 4
- solution 和 guess 仅包含"R","G","B","Y"这 4 种字符
题目思考
- 如何计算伪猜中次数?
解决方案
思路
- 分析题目, 我们可以很容易地计算出猜中次数, 即遍历下标, 查看当前位置的字符是否相等, 那如何计算伪猜中次数呢?
- 我们可以将剩余字符分别存入两个计数字典中, 然后遍历其中任意一个字典的 key, 查看该 key 是否也在另一个字典中
- 是的话则说明该字符同时出现在两个字符串中, 但位置不同, 属于伪猜中, 两者计数较小值即为当前字符伪猜中次数, 将其累加到最终结果里
- 下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N): 需要遍历 N 个字符 - 空间复杂度
O(N): 计数字典存最多 N 个字符
代码
class Solution:
def masterMind(self, solution: str, guess: str) -> List[int]:
# 需要两次遍历, 先计算完全正确的, 然后排除它们再计算其他的, 每个字符只能使用一次
res = [0, 0]
cs = collections.defaultdict(int)
cg = collections.defaultdict(int)
n = len(solution)
for i in range(n):
s, g = solution[i], guess[i]
if s == g:
# 完全匹配, 猜中次数加1
res[0] += 1
else:
# 非完全匹配, 加入计数字典
cs[s] += 1
cg[g] += 1
for s in cs:
if s in cg:
# 相同字符同时出现在两个字符串中, 但位置不同, 属于伪猜中, 两者计数较小值即为当前字符伪猜中次数
res[1] += min(cs[s], cg[s])
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号