LeetCode 面试题 16.15. 珠玑妙算
目录
题目描述
题意分析
solution与guess都由R、Y、G、B四种颜色组成且长度为 4。位置和颜色都相同叫“猜中”；颜色存在但位置不对叫“伪猜中”。每个槽位只能贡献一次，返回[猜中数, 伪猜中数]。难点是重复颜色。例如答案有一个 R、猜测有三个 R，最多只能匹配一个，不能按“guess 中每个字符是否出现在 solution”逐个累加。
可以把匹配拆成两层：先数位置完全相同的命中；再只看颜色多重集合的最大交集。对每种颜色 c，可匹配总数是
min(countSolution[c], countGuess[c])。这个总数包含真正猜中，因此最后减掉命中数就是伪猜中。
解法：精确命中 + 颜色频次交集
核心思路
一次扫描同时完成两件事：同下标字符相等就增加
hit；分别统计答案和猜测中四种颜色的频次。之后对 R、Y、G、B 求频次最小值之和，得到“忽略位置时最多能匹配多少颗珠子”
matched。不变量是：对每种颜色，任何合法配对都不可能超过两边频次的较小值，而这个上界可以实际达到，所以求和就是总匹配数。
pseudo = matched - hit。减法很关键，因为所有精确命中也被频次交集计算了一次。例：
solution = "RGBY"、guess = "GGRR"。只有下标 1 的 G 精确命中，所以hit = 1；颜色交集为一个 R 加一个 G，共 2；伪猜中为2 - 1 = 1，返回[1,1]。
解题步骤
- 初始化两个颜色频次表与
hit = 0。- 扫描四个位置：相同则增加 hit，同时更新两边颜色计数。
- 对四种颜色累加两张表的较小值，得到 matched。
- 返回
[hit, matched - hit]。
代码实现
class Solution {
public int[] masterMind(String solution, String guess) {
int x = 0, 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), 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)。
关键点总结
- 重复颜色意味着要按频次取交集，不能只判断“是否出现”。
- “总颜色匹配数减精确命中”把伪命中的一对一占用约束自然处理掉。
- 面试追问若要求一次遍历、一个计数表，可以先排除精确命中，再对未命中颜色用正负计数增量统计；当前双表写法更直观、证明更短。
- 题目长度固定为 4，但代码与推导可自然推广到任意长度和有限颜色集。
易错点总结
- 错误写法：伪猜中直接等于颜色交集。反例
solution="RGBY"、guess="GGRR"的颜色交集是 2，其中一个已经是精确命中；正确伪猜中只有 1。- 只用集合、不记录频次：
solution="RRGB"、guess="RRRR"最多匹配两个 R，集合写法可能错误计成四个。- 先删除命中位置却没有同步两边计数：命中的颜色会再次参与伪匹配，造成重复使用。
- 遍历颜色时漏掉一种：只统计 R/Y/G 而漏 B，
solution="BBBB"、guess="BBBB"会返回全 0 而不是[4,0]。- 把返回顺序写反：题目要求先命中、后伪命中，
[pseudo, hit]会直接判错。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 299. 猜数字游戏 | 中等 | Bulls 与 Cows，本题的数字版本 |
| 242. 有效的字母异位词 | 简单 | 有限字符集上的频次统计 |