LeetCode 第299题：猜数字游戏

📖 文章摘要

本文详细解析LeetCode第299题“猜数字游戏”，这是一道考察字符串处理和计数的中等难度题目。文章提供了哈希表和数组计数两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习字符串处理和计数算法的读者。

核心知识点： 字符串处理、哈希表、计数算法
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升字符串处理能力的开发者

题目描述

你在和朋友一起玩猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就要给他一个包含下述信息的提示：

猜中了多少个“公牛”（Bulls）：位置和数字都对的数字个数。
有多少个“奶牛”（Cows）：数字对但位置不对的数字个数。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 “xAyB” ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，位置不同的数字（奶牛）用 '?' 连接：
- 公牛：8
- 奶牛：0?1?7

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）是 1，数字对但位置不同（奶牛）是 1。

提示

1 <= secret.length, guess.length <= 1000
secret.length == guess.length
secret 和 guess 仅由数字组成

解题思路

本题可以使用两种方法来实现：

哈希表法：
- 第一次遍历统计公牛数量
- 使用哈希表记录剩余数字出现次数
- 第二次遍历统计奶牛数量
- 时间复杂度O(n)
数组计数法：
- 使用长度为10的数组记录数字出现次数
- 一次遍历同时统计公牛和奶牛
- 更高效的空间利用
- 时间复杂度O(n)

图解思路

计数过程分析表

步骤	操作	目的
1	统计公牛	找出位置和数字都匹配的情况
2	记录剩余数字	为统计奶牛做准备
3	统计奶牛	找出数字匹配但位置不同的情况
4	生成结果	按格式返回提示字符串

示例分析表

输入	公牛统计	奶牛统计	输出
“1807”/“7810”	1 (8)	3 (0,1,7)	“1A3B”
“1123”/“0111”	1 (1)	1 (1)	“1A1B”

代码实现

C# 实现

public class Solution {
    public string GetHint(string secret, string guess) {
        int bulls = 0;
        int[] secretCount = new int[10];
        int[] guessCount = new int[10];
        
        // 统计公牛和剩余数字
        for (int i = 0; i < secret.Length; i++) {
            if (secret[i] == guess[i]) {
                bulls++;
            } else {
                secretCount[secret[i] - '0']++;
                guessCount[guess[i] - '0']++;
            }
        }
        
        // 统计奶牛
        int cows = 0;
        for (int i = 0; i < 10; i++) {
            cows += Math.Min(secretCount[i], guessCount[i]);
        }
        
        return $"{bulls}A{cows}B";
    }
}

Python 实现

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = 0
        secret_count = [0] * 10
        guess_count = [0] * 10
        
        # 统计公牛和剩余数字
        for s, g in zip(secret, guess):
            if s == g:
                bulls += 1
            else:
                secret_count[int(s)] += 1
                guess_count[int(g)] += 1
        
        # 统计奶牛
        cows = sum(min(s, g) for s, g in zip(secret_count, guess_count))
        
        return f"{bulls}A{cows}B"

C++ 实现

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0;
        vector<int> secretCount(10);
        vector<int> guessCount(10);
        
        // 统计公牛和剩余数字
        for (int i = 0; i < secret.length(); i++) {
            if (secret[i] == guess[i]) {
                bulls++;
            } else {
                secretCount[secret[i] - '0']++;
                guessCount[guess[i] - '0']++;
            }
        }
        
        // 统计奶牛
        int cows = 0;
        for (int i = 0; i < 10; i++) {
            cows += min(secretCount[i], guessCount[i]);
        }
        
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

执行结果

C# 实现

执行用时：84 ms
内存消耗：36.2 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：0 ms
内存消耗：6.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	36.2 MB	代码结构清晰，性能适中
Python	36 ms	15.1 MB	实现简洁，内存占用小
C++	0 ms	6.4 MB	性能最优，内存占用最小

代码亮点

🎯 使用数组代替哈希表提升性能
💡 一次遍历同时处理公牛和奶牛
🔍 优化空间使用效率
🎨 代码结构清晰易懂

常见错误分析

🚫 重复计算相同数字
🚫 未考虑数字重复出现
🚫 公牛和奶牛计算顺序错误
🚫 字符串格式化错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表法	O(n)	O(n)	实现直观	空间消耗大
数组计数法	O(n)	O(1)	空间效率高	仅适用于数字

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第299题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

计数过程分析表

示例分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流