LeetCode 299中等哈希/字符串
猜数字游戏 图解题解
这道题到底在问什么
secret 与 guess 等长、只含数字。位置且数字都相同记一个公牛;数字存在但位置不同记一个奶牛(每个数字按出现次数配对)。返回形如 xAyB 的提示。
- 输入
- secret="1807", guess="7810"
- 输出
- "1A3B"
最优解：一步一步想明白
- 3记住「先逐位抓公牛,再对剩余数字计数取 min 抓奶牛」,下面每帧都在套它。
- 4比第 0 位：secret 是 1、guess 是 7。数字和位置都一样才算公牛。
- 5不相等，第 0 位不是公牛。它的数字留到第二步按计数找奶牛。
- 6比第 1 位：secret 是 8、guess 是 8。数字和位置都一样才算公牛。
- 7相等！第 1 位是公牛（绿色），公牛数加到 1。这位被「用掉」，不再参与奶牛统计。
- 8比第 2 位：secret 是 0、guess 是 1。数字和位置都一样才算公牛。
- 9不相等，第 2 位不是公牛。它的数字留到第二步按计数找奶牛。
- 10比第 3 位：secret 是 7、guess 是 0。数字和位置都一样才算公牛。
- 11不相等，第 3 位不是公牛。它的数字留到第二步按计数找奶牛。
- 12比第 4 位：secret 是 3、guess 是 3。数字和位置都一样才算公牛。
- 13相等！第 4 位是公牛（绿色），公牛数加到 2。这位被「用掉」，不再参与奶牛统计。
- 14比第 5 位：secret 是 4、guess 是 3。数字和位置都一样才算公牛。
- 15不相等，第 5 位不是公牛。它的数字留到第二步按计数找奶牛。
- 16比第 6 位：secret 是 5、guess 是 5。数字和位置都一样才算公牛。
- 17相等！第 6 位是公牛（绿色），公牛数加到 3。这位被「用掉」，不再参与奶牛统计。
- 18逐位扫完，公牛共 3 个(绿)。剩下 4 个没配上的位置(蓝)，按「数字」计数来数奶牛——不看位置，只看数字两边各剩几个。
- 19数字 0：非公牛位置里 secret 还剩 1 个、guess 还剩 1 个，能错位配上的是较小值 min(1, 1) = 1，奶牛累计到 1。
- 20数字 1：非公牛位置里 secret 还剩 1 个、guess 还剩 1 个，能错位配上的是较小值 min(1, 1) = 1，奶牛累计到 2。
- 21数字 3：非公牛位置里 secret 还剩 0 个、guess 还剩 1 个，能错位配上的是较小值 min(0, 1) = 0，奶牛累计到 2。
- 22数字 4：非公牛位置里 secret 还剩 1 个、guess 还剩 0 个，能错位配上的是较小值 min(1, 0) = 0，奶牛累计到 2。
- 23数字 7：非公牛位置里 secret 还剩 1 个、guess 还剩 1 个，能错位配上的是较小值 min(1, 1) = 1，奶牛累计到 3。
- 24汇总：公牛 3 个、奶牛 3 个，提示串就是 “3A3B”。公牛只看「位置+数字全对」，奶牛对剩余数字两边取 min。
⚠️ 容易写错的地方
✗ 错：把公牛位置也算进奶牛
✓ 对：公牛位置要排除在数字计数之外
否则会重复计数，奶牛偏多
✗ 错：奶牛按位置一一比对
✓ 对：奶牛按「数字计数取 min」
错位配对只关心两边各有几个该数字
✗ 错：忘了取 min
✓ 对：cows += min(cs[d], cg[d])
只有较少的一方才能全部配上对
完整代码（Python / C++ / Java）
Python
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = 0
cs = [0] * 10
cg = [0] * 10
for a, b in zip(secret, guess):
if a == b:
bulls += 1
else:
cs[ord(a) - 48] += 1
cg[ord(b) - 48] += 1
cows = sum(min(a, b) for a, b in zip(cs, cg))
return f"{bulls}A{cows}B"C++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0;
vector<int> cs(10), cg(10);
for (int i = 0; i < (int)secret.size(); ++i) {
if (secret[i] == guess[i]) bulls++;
else { cs[secret[i]-'0']++; cg[guess[i]-'0']++; }
}
int cows = 0;
for (int i = 0; i < 10; ++i) cows += min(cs[i], cg[i]);
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};Java
import java.util.*;
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0;
int[] cs = new int[10], cg = new int[10];
for (int i = 0; i < secret.length(); i++) {
char a = secret.charAt(i), b = guess.charAt(i);
if (a == b) bulls++;
else { cs[a - '0']++; cg[b - '0']++; }
}
int cows = 0;
for (int i = 0; i < 10; i++) cows += Math.min(cs[i], cg[i]);
return bulls + "A" + cows + "B";
}
}复杂度
时间
O(n)
一遍比对 + 10 个数字汇总
空间
O(1)
两个长度 10 的计数数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 猜数字游戏 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能一遍遍历同时数公牛和奶牛？+
可以。维护两个计数数组,遍历时:位置相等 bulls++;否则对 secret 数字,如果之前 guess 那边已出现过(cg[d]>0)就 cows++ 并 cg[d]--,反之亦然(用一个数组带正负号也行)。本题先分两步更直观,一遍法是其等价优化。
如果不是数字而是任意字符怎么办？+
把长度 10 的计数桶换成哈希表(字符→计数)即可,逻辑完全一样:位置同记公牛,否则两边计数最后取 min 求奶牛。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 猜数字游戏 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。