299. 猜数字游戏
题目描述
你和朋友玩猜数字游戏（Bulls and Cows）。你心里有一个秘密数字 secret，朋友给出一个猜测 guess，两者长度相同，都由数字字符组成，并且都可能有重复数字。
每猜一次，你要回一个提示，包括两个数：公牛数 x，即数字和位置都对上的位数；奶牛数 y，即在排除公牛位之后，guess 中还有多少位可以通过调整位置变成公牛。重复的数字按个数配对，同一个数字不能被重复计算。
按 "xAyB" 的格式返回提示字符串，其中 A 代表公牛，B 代表奶牛。
示例 1
输入：secret = "1807", guess = "7810" 输出："1A3B"
解释：第 2 位的 8 是公牛；剩下的 1、0、7 都出现在 secret 中，只是位置不对，是 3 头奶牛。
示例 2
输入：secret = "1123", guess = "0111" 输出："1A1B"
解释：第 2 位的 1 是公牛；其余位置里 secret 还剩一个 1，guess 还剩两个 1，只能配上一对，所以只有 1 头奶牛。
数据范围
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret和guess只含数字。
解题思路
一遍扫描：同一位置数字相同就是公牛；否则把 secret 的数字计入 cs，guess 的数字计入 cg，这些是“未匹配”的数字。扫完后，对每个数字 d，双方都未匹配的那一部分最多能配成 min(cs[d], cg[d]) 对，求和就是奶牛数。
为什么正确
cs[d] 和 cg[d] 只统计不是公牛的位置，所以公牛不会被重复算成奶牛。
复杂度分析
时间 O(n)；空间 O(10)。
易错点
不能对每个 guess 数字去 secret 里“找有没有”：重复数字会被多次计数，公牛也会被重复算成奶牛。必须只统计非公牛位置，再取 min。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = 0
cs, cg = [0] * 10, [0] * 10
for a, b in zip(secret, guess):
if a == b:
bulls += 1
else:
cs[int(a)] += 1
cg[int(b)] += 1
cows = sum(min(cs[d], cg[d]) for d in range(10))
return f'{bulls}A{cows}B'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++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls += 1;
} else {
cs[secret.charAt(i) - '0'] += 1;
cg[guess.charAt(i) - '0'] += 1;
}
}
int cows = 0;
for (int d = 0; d < 10; d++) cows += Math.min(cs[d], cg[d]);
return bulls + "A" + cows + "B";
}
}class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0;
vector<int> cs(10, 0), cg(10, 0);
for (size_t i = 0; i < secret.size(); i++) {
if (secret[i] == guess[i]) {
bulls += 1;
} else {
cs[secret[i] - '0'] += 1;
cg[guess[i] - '0'] += 1;
}
}
int cows = 0;
for (int d = 0; d < 10; d++) cows += min(cs[d], cg[d]);
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};func getHint(secret string, guess string) string {
bulls := 0
cs, cg := make([]int, 10), make([]int, 10)
for i := 0; i < len(secret); i++ {
if secret[i] == guess[i] {
bulls += 1
} else {
cs[secret[i]-'0'] += 1
cg[guess[i]-'0'] += 1
}
}
cows := 0
for d := 0; d < 10; d++ {
if cs[d] < cg[d] {
cows += cs[d]
} else {
cows += cg[d]
}
}
return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B"
}var getHint = function(secret, guess) {
let bulls = 0;
const cs = new Array(10).fill(0), cg = new Array(10).fill(0);
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls += 1;
} else {
cs[+secret[i]] += 1;
cg[+guess[i]] += 1;
}
}
let cows = 0;
for (let d = 0; d < 10; d++) cows += Math.min(cs[d], cg[d]);
return `${bulls}A${cows}B`;
};function getHint(secret: string, guess: string): string {
let bulls = 0;
const cs: number[] = new Array(10).fill(0), cg: number[] = new Array(10).fill(0);
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls += 1;
} else {
cs[+secret[i]] += 1;
cg[+guess[i]] += 1;
}
}
let cows = 0;
for (let d = 0; d < 10; d++) cows += Math.min(cs[d], cg[d]);
return `${bulls}A${cows}B`;
}