猜数字游戏

标签: 哈希表 字符串 计数

难度: Medium

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

  • 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
  • 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

提示：

  • 1 <= secret.length, guess.length <= 1000
  • secret.length == guess.length
  • secret 和 guess 仅由数字组成

Submission

运行时间: 24 ms

内存: 0.0 MB

from collections import defaultdict

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        count_a , count_b, secret_dict, guess_dict = 0, 0, defaultdict(int), defaultdict(int)
        for i, s in enumerate(secret):
            g = guess[i]
            if s == g:
                count_a += 1
                continue
            secret_dict[s] += 1
            guess_dict[g] += 1
        for k in guess_dict:
            if secret_dict[k] >= guess_dict[k]:
                count_b += guess_dict[k]
            else:
                count_b += secret_dict[k]

        return "{}A{}B".format(count_a, count_b)

Explain

此题解采用了两个主要步骤来解决猜数字游戏问题。首先，遍历秘密数字和猜测数字的每一位，比较对应位置的数字。如果数字相同，则这是一个公牛（Bull），计数器count_a增加。如果不同，将秘密数字和猜测数字的这一位分别记录到两个字典中，用来记录各数字出现的次数。在第一次遍历完成后，再次遍历记录的猜测数字的字典，对于字典中的每一个数字，检查它在秘密数字字典中的数量，以此来确定奶牛（Cow）的数量。奶牛的数量是由猜对的数字但位置不对的次数决定的，计算方法为两个字典中对应数字的最小出现次数之和。

时间复杂度: O(n)

空间复杂度: O(1)

from collections import defaultdict

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        count_a , count_b, secret_dict, guess_dict = 0, 0, defaultdict(int), defaultdict(int)
        # 遍历每一位，检查公牛并记录非匹配数字
        for i, s in enumerate(secret):
            g = guess[i]
            if s == g:
                count_a += 1  # 相同位置且数字相同，增加公牛计数
                continue
            secret_dict[s] += 1  # 记录秘密数字中的非匹配数字
            guess_dict[g] += 1  # 记录猜测中的非匹配数字
        # 计算奶牛的数量
        for k in guess_dict:
            if secret_dict[k] >= guess_dict[k]:
                count_b += guess_dict[k]
            else:
                count_b += secret_dict[k]

        return "{}A{}B".format(count_a, count_b)

Explore

在算法中，直接增加公牛计数是因为公牛的定义是位置和数字都正确，这是可以立即确认的。将不匹配的数字存储在字典中的原因是为了后续处理奶牛的计算。这种方法的优势在于它可以有效地分离公牛和奶牛的计算，简化逻辑：先确定所有的公牛，然后用剩下的不匹配数字来确定奶牛的数量。这样做可以避免混淆两种计数，并且能更准确地管理每种数字的出现次数。

在算法中，每当发现位置和数字都匹配（即公牛），就会跳过这对数字的后续处理，不把它们添加到字典中。因此，这些已经计算为公牛的数字不会出现在后续用来计算奶牛的字典中。这样可以确保在计算奶牛时，只计算那些位置不匹配但数字正确的情况，避免重复计算已作为公牛的数字。

在此算法中选用defaultdict进行字典初始化是因为它自动为不存在的键创建默认值（在本题中是0）。这样当增加一个数字的计数时，不需要先检查键是否存在，直接增加即可。相比之下，使用普通字典时，如果键不存在，需要先初始化一个键值对，这会增加代码的复杂度和出错的可能性。defaultdict使代码更简洁且易于理解。

这种计算逻辑基于奶牛的定义：数字正确但位置不对。当两个字典中的某个数字的出现次数不一致时，表示有重叠但不完全匹配的情况。取两个字典中该数字出现次数的最小值确保不会超过实际匹配的可能性，因此这个最小值代表了能够成为奶牛的最大数量。这样做是为了确保每个数字被计算的次数与它在对方数字中实际能匹配的次数相对应。