LeetCode第299题_猜数字游戏

技术文档

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题。

💬 互动交流

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

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

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

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

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

LeetCode第299题_猜数字游戏