LeetCode 299. 猜数字游戏
题目描述
题意分析
两个等长字符串只包含数字。相同位置的数字也相同，计为一头公牛；排除这些位置后，剩余数字能与另一串中的相同数字配对，计为奶牛。每次数字出现只能使用一次，重复数字也要按实际次数匹配。
最后返回
xAyB，其中x是公牛数，y是奶牛数。字符串可能含前导零，应直接按字符比较，不必转成整数。
解法：计数比较
核心思路
[!blue]
公牛的位置已经确定，先逐位比较两串。遇到相同数字就增加公牛数，并把这个位置同时从后续匹配中排除，避免它再次被计为奶牛。
对其余位置，分别用
cntS[d]和cntG[d]记录数字d在秘密串和猜测串中还剩多少次。某种数字能匹配的数量恰好是两侧剩余次数的较小值：每次配对都要消耗两侧各一次，多出来的一侧没有对应数字可配。剩余位置的同下标字符都不同，因此按相同数字配出的任何一对都不会是公牛。各个数字之间互不争用次数，将
0到9的最小频次相加，就是奶牛总数。
解题步骤
- 初始化公牛数
bulls，以及两个长度为10的剩余频次数组。- 同步遍历
secret和guess：相同位置数字相同则bulls加一，否则分别增加两串对应数字的频次。- 对每个数字累加
min(cntS[d], cntG[d])，得到奶牛数cows。- 将两项计数按十进制形式拼接为
bulls + "A" + cows + "B"。
代码实现
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";
}
}
import "fmt"
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)$，扫描加固定十项汇总。
- 空间复杂度：$O(1)$ 辅助空间，固定两组数字频次，不计返回文本。
关键点总结
[!green]
- 先认领公牛，再匹配剩余数字，保证一个位置不会重复贡献。
- 奶牛数量由每种数字两侧的剩余次数共同限制，不能只记录是否出现。
- 排除公牛后，匹配过程只关心频次，不再需要寻找具体位置。
易错点总结
[!yellow]
- 公牛位置不要再放入频次数组，否则同一对字符会被重复计数。
- 奶牛不能直接取猜测串的出现次数，秘密串中可能没有足够的剩余数字可供配对。
- 两串题目保证等长，可同步遍历；不能把字符串转为整数后丢掉前导零和位置信息。
- Go 的
string(整数)表示码点转换，不是十进制数字格式化；这里使用fmt.Sprintf生成结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 350. 两个数组的交集 II | 简单 | 忽略位置的全部匹配数是频次最小值之和，再减去位置已匹配者得到伪命中。 |
| 438. 找到字符串中所有字母异位词 | 中等 | 同样要按字符频次处理重复，不能仅用字符集合判断是否出现。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！