LeetCode 面试题 16.15. 珠玑妙算

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
字符串 哈希表 计数

题目描述

✅ 面试题 16.15. 珠玑妙算

image-20260929010319994

题意分析

solution 与 guess 都由 R、Y、G、B 四种颜色组成且长度为 4。位置和颜色都相同叫“猜中”；颜色存在但位置不对叫“伪猜中”。每个槽位只能贡献一次，返回 [猜中数, 伪猜中数]。

颜色可以重复，但一个球只能匹配一次，因此必须比较数量，不能只判断某种颜色是否出现。精确命中的球还要优先占用，不能再次计入伪猜中。

可以把匹配拆成两层：先数位置完全相同的命中；再只看颜色多重集合的最大交集。对每种颜色 c，可匹配总数是 min(countSolution[c], countGuess[c])。这个总数包含真正猜中，因此最后减掉命中数就是伪猜中。

解法：精确命中 + 颜色频次交集

核心思路

[!blue]

一次扫描同时统计精确命中和两边的颜色频次。代码用 x 保存精确命中数：只有同下标字符相同才增加；cnt1、cnt2 则记录四种颜色各有多少个，包括已经精确命中的球。

忽略位置时，某种颜色在两边分别有 a、b 个，最多且恰好能配成 min(a, b) 对。对四种颜色求和得到总颜色匹配数，代码保存为 y。多出来的同色球没有另一侧的球可配，不会被重复计算。

总匹配数已经包含精确命中，因此伪猜中数为 y - x。若某种颜色有 h 个精确命中，先排除它们再配对，剩余可匹配数为 min(a - h, b - h) = min(a, b) - h；对所有颜色求和，正好得到“总匹配数减精确命中数”。排除精确命中后，两边同一位置不可能再是相同颜色，剩余配对都是伪猜中。

全部位置猜中时，x 与 y 都为 4，伪猜中自然为 0；两边没有共同颜色时，两种计数也都为 0，无需额外分支。

解题步骤

  1. 初始化两张颜色频次表，令 x = 0、y = 0。
  2. 扫描四个位置：相同则增加 x，同时更新两边颜色计数。
  3. 对四种颜色累加两张表中的较小频次，保存到 y。
  4. 按题目顺序返回 [x, y - x]，先精确命中，后伪猜中。

代码实现

class Solution {
    public int[] masterMind(String solution, String guess) {
        int x = 0;
        int y = 0;
        Map<Character, Integer> cnt1 = new HashMap<>();
        Map<Character, Integer> cnt2 = new HashMap<>();

        for (int i = 0; i < 4; ++i) {
            char a = solution.charAt(i);
            char b = guess.charAt(i);

            x += a == b ? 1 : 0;
            cnt1.merge(a, 1, Integer::sum);
            cnt2.merge(b, 1, Integer::sum);
        }

        for (char c : "RYGB".toCharArray()) {
            y += Math.min(cnt1.getOrDefault(c, 0), cnt2.getOrDefault(c, 0));
        }

        return new int[] {
            x,
            y - x
        };
    }
}

func masterMind(solution string, guess string) []int {
    var x, y int
    cnt1 := map[byte]int{}
    cnt2 := map[byte]int{}
    for i := range solution {
        a, b := solution[i], guess[i]
        if a == b {
            x++
        }
        cnt1[a]++
        cnt2[b]++
    }
    for _, c := range []byte("RYGB") {
        y += min(cnt1[c], cnt2[c])
    }
    return []int{
        x,
        y - x,
    }
}

复杂度分析

  • 时间复杂度：O(L + C)，L 为字符串长度、C 为颜色种数；本题 L=C=4，因此是 O(1)。
  • 空间复杂度：O(C)，本题只有四种颜色，可视为 O(1)。

关键点总结

[!green]

  • 重复颜色意味着要按频次取交集，不能只判断“是否出现”。
  • “总颜色匹配数减精确命中”把伪命中的一对一占用约束自然处理掉。
  • 两边同步去掉一个精确命中，会让该颜色的频次交集恰好减少 1，这是最后相减的依据。

易错点总结

[!yellow]

  • 伪猜中直接等于颜色交集：会把精确命中重复算入伪猜中。
  • 只用集合、不记录频次：会把一侧多余的同色球也当成可匹配对象。
  • 先删除命中位置却没有同步两边计数：命中的颜色会再次参与伪匹配，造成重复使用。
  • 遍历颜色时漏掉一种：总匹配数可能小于已经统计的精确命中数，导致错误结果。
  • 把返回顺序写反：题目要求先命中、后伪命中，[pseudo, hit] 会直接判错。

相似题目

题目 难度 关联与区别
350. 两个数组的交集 II 简单 同样用两侧频次最小值求多重集合交集，本题再减掉位置已经精确匹配的部分。
438. 找到字符串中所有字母异位词 中等 同样依据频次匹配而非仅依据字符是否出现，原题还需维护移动窗口。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63884870
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！