DeepSeek LeetCode 299. 猜数字游戏 Java实现

LeetCode 299. 猜数字游戏

题目分析

给定 secret 和 guess 两个等长字符串（只含数字），需要统计：

· Bulls（A）：数字和位置都正确的个数
· Cows（B）：数字正确但位置不对的个数

关键点：两个字符串都可能含有重复数字，所以 Cows 只能通过「频次取最小」来计算，不能简单用集合。

解法一：两次遍历（推荐，最直观）

思路：

class Solution {
public String getHint(String secret, String guess) {
int[] secretCount = new int[10];
int[] guessCount = new int[10];
int bulls = 0;
int cows = 0;

for (int i = 0; i < secret.length(); i++) {
char s = secret.charAt(i);
char g = guess.charAt(i);
if (s == g) {
bulls++;
} else {
secretCount[s – '0']++;
guessCount[g – '0']++;
}
}

for (int d = 0; d < 10; d++) {
cows += Math.min(secretCount[d], guessCount[d]);
}

return bulls + "A" + cows + "B";
}
}

复杂度：时间 O(n)，空间 O(1)（固定 10 个桶）。

解法二：一次遍历（技巧性强）

思路：用一个 count 数组表示「secret 相对 guess 多出来的数字数量」。

· count[d] > 0：secret 中数字 d 多出来了，等着后面 guess 出现 d 来配对
· count[d] < 0：guess 中数字 d 多出来了，等着后面 secret 出现 d 来配对

遍历时，遇到 s != g：

· 若 count[s] < 0，说明之前 guess 里有多余的 s，现在可以配对 → cows++
· 若 count[g] > 0，说明之前 secret 里有多余的 g，现在可以配对 → cows++
· 更新 count[s]++，count[g]–

class Solution {
public String getHint(String secret, String guess) {
int[] count = new int[10];
int bulls = 0, cows = 0;

for (int i = 0; i < secret.length(); i++) {
int s = secret.charAt(i) – '0';
int g = guess.charAt(i) – '0';

if (s == g) {
bulls++;
} else {
if (count[s] < 0) cows++; // guess 中之前多了 s，现在配上
if (count[g] > 0) cows++; // secret 中之前多了 g，现在配上
count[s]++;
count[g]—;
}
}

return bulls + "A" + cows + "B";
}
}

复杂度：时间 O(n)，空间 O(1)。

示例验证

输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释:
1 个公牛 (位置 1 的 '8')
3 个奶牛 ('0','1','7' 数字对但位置错)

输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释:
1 个公牛 (位置 2 的 '1' 在索引 1 处匹配)
1 个奶牛 (secret 剩下的 '1' 和 guess 的 '1')
注意重复数字：secret 有 2 个 '1'，guess 有 3 个 '1'，去掉公牛的 1 个后，
两边剩余各 1 个和 2 个，取 min = 1。

易错点提醒

两种解法都可 AC，解法一更易理解和书写，解法二更优雅但需要理解 count 数组的正负含义。