0299. Bulls and Cows
====================
题目信息
--------
:题号: 0299
:难度: Medium
:主题: 数字字符串、位置匹配、重复数字计数
:原题: `LeetCode 0299 `_
:重点: 数字和位置都相同计为 bull、数字相同但位置不同计为 cow、每个字符位置最多参与一次匹配
题目重述
--------
给定两个等长的数字字符串 ``secret`` 和 ``guess``。逐位比较时,数字相同且位置也相同的字符称为 bull;排除所有 bull 后,如果 ``guess`` 中某个数字还能与 ``secret`` 中不同位置的同值数字配对,则该配对称为 cow。
每个字符位置最多只能被匹配一次,因此重复数字的 cow 数量取决于双方未同位匹配部分中该数字出现次数的较小值。返回格式固定为 ``"xAyB"``,其中 ``x`` 是 bull 数量,``y`` 是 cow 数量。
两个字符串长度相同且位于 ``[1, 1000]``,只包含字符 ``'0'`` 到 ``'9'``,允许出现重复数字。函数不需要返回哪些位置构成匹配。
自建示例
--------
除一个同位数字外,其余数字都在错误位置:
.. code-block:: text
输入:secret = "2210",guess = "1202"
输出:"1A3B"
解释:第二位的 2 是一个 bull;排除它后,剩余的 2、1、0 都能在 guess 的不同位置找到一次匹配,因此有三个 cows。
重复猜测不能超过秘密中的剩余数量:
.. code-block:: text
输入:secret = "3305",guess = "3333"
输出:"2A0B"
解释:前两个 3 在相同位置形成两个 bulls;secret 的其余位置没有 3,所以后两个猜测 3 不能再形成 cow。
先匹配位置,再匹配剩余频次
------------------------
第一遍只处理同位置同数字的字符,计入 ``bulls``,这些位置不能再次参与 cow。
对其余位置分别统计 ``secret`` 与 ``guess`` 中每个数字的出现次数;数字 ``d`` 能形成的 cow 数量就是
两边剩余频次的较小值,十个数字的这些最小值相加。
分两步是关键。若先把所有相同数字都按频次配对,会把本应计为 bull 的位置也算进 cow,
或者在重复数字场景中超额匹配。
正确性说明
----------
同位相等的位置显然是 bulls,先排除它们后,剩余两串中的任意匹配都必须位置不同。
固定数字 ``d``,秘密串剩余部分最多提供 ``secret_count[d]`` 个,猜测串最多需要
``guess_count[d]`` 个,且每次匹配只消耗双方一个位置,因此可配对数量恰为两者最小值。
十个数字互不冲突,求和得到准确 cows。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::string getHint(const std::string& secret,
const std::string& guess) {
int bulls = 0;
int secret_count[10] = {};
int guess_count[10] = {};
for (int i = 0; i < static_cast(secret.size()); ++i) {
if (secret[i] == guess[i]) {
++bulls;
} else {
++secret_count[secret[i] - '0'];
++guess_count[guess[i] - '0'];
}
}
int cows = 0;
for (int digit = 0; digit < 10; ++digit) {
cows += std::min(secret_count[digit], guess_count[digit]);
}
return std::to_string(bulls) + "A" +
std::to_string(cows) + "B";
}
};
代码分析
--------
扫描字符串并检查 10 个频次桶,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。
字符串长度由题目保证相同;输出按固定 ``xAyB`` 格式拼接,不依赖匹配位置的具体顺序。