299. 猜数字游戏

image-20211108101910571

解题思路：

​ 这题公牛是比较好求的，遍历secret和guess判断对应字符是否相等即可，但是奶牛的思路需要转换，题目中的含义是数字猜对但是位置不对，这里可以分为两种情况。

  1. 在对应位置上不相同时，secret中该数字的出现次数比guess少，这时对于guess来说只能填补secret字符中该数字的个数，guess多出字符无用，所以结果应取secret中该数字的次数
  2. 在对应位置上不相同时，secret中该数字的出现次数比guess多，这时对于guess来说只能填补自身数量的secret字符，secret多出字符无用，所以结果应取guess中该数字出现的次数

综上所述其实可以把奶牛的求解通过这样的方式：用哈希表arr1和arr2分别存储secret和guess中对应数字的存储次数，而后对于每个数字来说求arr1与arr2中对应数字的最小值，其的和为奶牛的个数。

以下是C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string getHint(string secret, string guess) {
        //用两个哈希表分别存储secret和guess的对应数字的个数
        int len=secret.size();
        int arr1[10]={0},arr2[10]={0};
        int ANum=0;
        for(int i=0;i<len;i++){
            if(secret[i]==guess[i]){
                ++ANum;
                continue;
            }
            arr1[secret[i]-'0']++;
            arr2[guess[i]-'0']++;
        }

        //找到arr1和arr2中对应数字的最小值
        int BNum=0;
        for(int i=0;i<10;i++){
            BNum+=min(arr1[i],arr2[i]);
        }

        //组合答案
        return to_string(ANum)+"A"+to_string(BNum)+"B";
    }
};