LeetCode 299. 猜数字游戏

2026-05-22 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 299. 猜数字游戏

题意分析

给两个等长的数字串 secret 和 guess，统计两类信息：公牛是「数字对、位置也对」的个数，奶牛是「数字在 secret 里出现过、但位置不对」的个数，最后按 xAyB 的格式返回。

关键约束是「每个字符只能被算一次」：已经被判为公牛的位置不能再参与奶牛统计，一个 secret 里的数字也不能同时被 guess 里的两个字符认领。这条规则决定了奶牛数不是简单的「相同数字个数」，而是两边剩余计数的逐位取最小值再求和。

两串等长且只含数字字符 0 到 9，这是一条很有价值的约束：字符集只有 10 种，可以用两个长度为 10 的定长数组做计数，比哈希表更快也更好写。

边界包括：串中有大量重复数字时的配额分配；公牛数为 0 或奶牛数为 0 的情形；完全相同的两串应返回 nA0B。

解法：计数比较

核心思路

朴素做法是先扫一遍标出所有公牛，然后对每个非公牛的 guess 字符去 secret 的剩余字符里线性查找并删除。这样是对的，但查找与删除都要扫剩余部分，退化成 $O(n^2)$，而且还要维护「已被认领」的标记数组，实现琐碎。

瓶颈同样在于「逐个匹配」。观察奶牛的定义会发现，它与位置完全无关——只要把公牛占掉的字符排除干净，剩下的就是两个多重集合的匹配问题：对每个数字 d，能配成奶牛的对数就是「secret 剩余里 d 的个数」与「guess 剩余里 d 的个数」中的较小者，因为配对受两边共同限制。把 10 个数字的这个最小值加起来就是奶牛总数。

于是一趟遍历同时做两件事：位置相同就计入公牛；位置不同就把 secret 的字符和 guess 的字符分别记进各自的计数数组。这样计数数组里天然只剩下「未被公牛占用」的字符，不需要事后再扣。

由此得到的不变量是：扫描到第 i 位时，bulls 是前 i 位中位置与数字都相同的个数，而 cntS 与 cntG 分别是前 i 位里两串各自「未参与公牛配对」的字符频次。这条不变量保证了第二阶段取 min 求和时，两边的配额都是干净的剩余量，不会与公牛重复计数。

最后按 bulls + "A" + cows + "B" 拼接返回。整个过程只需一趟扫描加一次长度 10 的汇总。

解题步骤

准备变量 bulls 和两个长度为 10 的计数数组 cntS、cntG。长度取 10 是因为字符集限定为数字，用 c - '0' 直接映射下标，省掉哈希开销。

同步遍历两串的相同下标。两串等长是题目保证的，所以可以用同一个下标推进，不需要双指针。

若当前位两字符相同，bulls 加一，且不做任何计数。跳过计数正是「公牛不参与奶牛统计」的落地方式，比事后再从计数里扣掉更不容易出错。

若不同，把 secret 的字符记进 cntS、guess 的字符记进 cntG。两边各记各的，此时还不知道它们将来会和谁配对。

遍历结束后，对 0 到 9 每个数字取 min(cntS[d], cntG[d]) 并累加得到 cows。取最小值的理由是配对必须两边都有货，供给少的一方决定了对数。

按格式拼接字符串返回。

以 secret = "1807"、guess = "7810" 走一遍。

i = 0：'1' 与 '7' 不同，cntS[1] 变成 1，cntG[7] 变成 1。i = 1：'8' 与 '8' 相同，bulls 变成 1，两个计数数组都不动。i = 2：'0' 与 '1' 不同，cntS[0] 变成 1，cntG[1] 变成 1。i = 3：'7' 与 '0' 不同，cntS[7] 变成 1，cntG[0] 变成 1。

此时 cntS 在下标 0、1、7 处各为 1，cntG 在下标 0、1、7 处也各为 1。汇总：数字 0 取 min(1,1) = 1，数字 1 取 min(1,1) = 1，数字 7 取 min(1,1) = 1，其余为 0，cows = 3。

返回 "1A3B"，与题目样例一致。注意数字 8 完全没有进入计数数组，因为它已经被判为公牛——这正是不变量在起作用。

再用重复数字的用例 secret = "1123"、guess = "0111" 检验配额分配。i = 0：'1' 与 '0' 不同，cntS[1] = 1，cntG[0] = 1。i = 1：'1' 与 '1' 相同，bulls = 1。i = 2：'2' 与 '1' 不同，cntS[2] = 1，cntG[1] = 1。i = 3：'3' 与 '1' 不同，cntS[3] = 1，cntG[1] = 2。汇总时数字 1 取 min(1, 2) = 1，其余数字两边不重合都取 0，cows = 1，返回 "1A1B"，与官方样例一致。若不取最小值而是直接累加 cntG[1]，就会得到 2，把 secret 中并不存在的第二个可用的 1 也算了进去。

代码实现

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] cntS = new int[10];
        int[] cntG = new int[10];

        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                bulls++;
            } else {
                cntS[s - '0']++;
                cntG[g - '0']++;
            }
        }

        int cows = 0;
        for (int i = 0; i < 10; i++) {
            cows += Math.min(cntS[i], cntG[i]);
        }

        return bulls + "A" + cows + "B";
    }
}

func getHint(secret string, guess string) string {
    bulls := 0
    cntS := make([]int, 10)
    cntG := make([]int, 10)

    for i := 0; i < len(secret); i++ {
        s := secret[i]
        g := guess[i]
        if s == g {
            bulls++
        } else {
            cntS[s-'0']++
            cntG[g-'0']++
        }
    }

    cows := 0
    for i := 0; i < 10; i++ {
        if cntS[i] < cntG[i] {
            cows += cntS[i]
        } else {
            cows += cntG[i]
        }
    }

    return fmt.Sprintf("%dA%dB", bulls, cows)
}

复杂度分析

时间复杂度：$O(n)$，一趟遍历同时统计公牛与剩余频次，汇总阶段固定循环 10 次，与 n 无关。

空间复杂度：$O(1)$，两个长度为 10 的计数数组是常量级；返回的结果串不计入额外空间。

关键点总结

「位置相关」和「位置无关」的统计要分开处理：先一趟扫描把位置相关的部分（公牛）摘干净，剩下的就退化成纯粹的多重集合匹配，用计数取最小值即可。

排除已配对元素的最优做法是「一开始就不计入」，而不是「先全统计再扣减」；前者靠不变量天然正确，后者极易在重复元素上扣错。

两个多重集合能配成多少对，答案永远是逐元素取 min 后求和，供给少的一方是瓶颈——这个结论在赎金信、字符重排、糖果分配等题里反复出现。

字符集有限（这里是 10 个数字）时用定长数组代替哈希表，代码更短、常数更小，也不需要处理键不存在的情况。

面试视角：面试官最想看的是你能不能一趟扫描完成统计。若你先写了「两趟：先标公牛再统计」的版本，要主动指出可以合并成一趟；被追问「如果字符集是任意 Unicode」就换成哈希表，思路完全不变；被追问「能否只用一个计数数组」则可以给出经典技巧——用同一个数组，secret 的字符做加、guess 的字符做减，加之前若已为负说明能配对，减之前若已为正同理，这样能把空间再砍一半。

易错点总结

错误写法：奶牛统计时直接累加 cntG[i] 而不取最小值 → 用例 secret = "1123", guess = "0111"，guess 里有两个多余的 1 但 secret 只剩一个，返回 "1A2B"，正确答案是 "1A1B"。

错误写法：公牛位置也计入两个计数数组 → 用例 secret = "1807", guess = "7810"，数字 8 被同时算成公牛和奶牛，返回 "1A4B"，正确答案是 "1A3B"。

错误写法：先统计全部频次取 min 得到总匹配数，却忘了再减去公牛数 → 用例 secret = "1122", guess = "1222"，总匹配是 3、公牛也是 3，返回 "3A3B"，正确答案是 "3A0B"。

错误写法：把奶牛判定写成「guess 的字符在 secret 中出现过就算一次」 → 用例 secret = "1122", guess = "1111"，后两个 1 因为 secret 里含 1 而被算成奶牛，返回 "2A2B"，正确答案是 "2A0B"。

错误写法：用一个共享数组同时给两串计数（都做加法） → 用例 secret = "1807", guess = "7810"，加完之后无法区分哪一半来自哪个串，取 min 失去意义。

错误写法：结果格式写成 bulls + "B" + cows + "A" 或用中文分隔 → 用例任意，输出串与判题期望不符，直接判错。

错误写法：Java 里写成 bulls + "A" + cows + "B" 之外的 "" + bulls + 'A' + cows + 'B' 且顺序不当，如 bulls + 'A' 开头 → char 与 int 相加得到的是数值而非拼接，用例 bulls = 1 时会输出 66 开头的乱码串。

错误写法：假设两串可能不等长而用 guess.length() 做循环上界 → 题目保证等长，但若真按 guess 遍历且 guess 更长，用例中访问 secret.charAt(i) 会越界抛异常。

错误写法：计数数组开成长度 26 并用 c - 'a' 映射 → 用例 secret = "1807"，数字字符减去 'a' 得到负数下标，直接数组越界。

错误写法：Go 里用 string(bulls) + "A" + string(cows) + "B" 拼接 → string(1) 得到的是码点 1 的控制字符而不是字符 '1'，输出是一串乱码，必须用 fmt.Sprintf 或 strconv.Itoa。

错误写法：认为公牛和奶牛之和一定等于串长 → 用例 secret = "1234", guess = "5678"，返回值应是 "0A0B"，任何基于总数补齐的写法都会算出错误的奶牛数。

相似题目

题目	难度	考察点
面试题 16.15. 珠玑妙算	简单	完全同型的猜色游戏，字符集换成四个字母
383. 赎金信	简单	只需判断一方能否被另一方覆盖，比较方向是单向的
242. 有效的字母异位词	简单	要求两边频次完全相等，可用一加一减后检查是否全零
387. 字符串中的第一个唯一字符	简单	计数之后需按原顺序二次遍历定位，位置信息不能丢
389. 找不同	简单	只差一个字符，可用异或或求和差把空间降到常数
面试题 01.02. 判定是否互为字符重排	简单	同为频次比较，但字符集是 ASCII，数组要开到 128