LeetCode-299 Bulls and Cows

题目描述

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. 

Please note that both secret number and friend's guess may contain duplicate digits.

题目大意

给定两个长度相同且只包含数字的字符串，两个字符串相同位置数字相同则记为一个bull，如果第二个字符串中出现了第一个字符串中的某个字符但位置不同，则记为一个cow。要求将bull的数值和cow的数值整合为一个字符串返回，用A表示bull，B表示cow （例如5个bull，2个cow则表示为“1A2B”）。

示例

E1

E2

解题思路

先遍历一遍两个字符串，将同位置相同数字的个数记录，使bull加一，同时将其余位置的数字的个数利用map进行保存。

再遍历一遍第二个字符串，依次查找map，如果找到且该map表示的数值不为0，则代表第一个字符串中出现了该数字，将cow加一。

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

代码

class Solution {
public:
    string getHint(string secret, string guess) {
        int len = secret.length(), bull = 0, cow = 0;
        // 遍历两个字符串
        for(int i = 0; i < len; ++i) {
            // 如果同位置的数字相等，则将bull加一，同时将guess[i]设为‘#’，为了第二遍 
            // 遍历的时候将bull误算为cow
            if(secret[i] == guess[i]) {
                ++bull;
                guess[i] = '#';
            }
            // 若不相等，则将该位置数字记录到map中，使表示该数字的个数加一
            else {
                ++pos[secret[i]];
            }
        }
        // 遍历第二个字符串
        for(int i = 0; i < len; ++i) {
            // 若为‘#’，则表示这个位置为之前得到的bull，跳过即可
            if(guess[i] == '#')
                continue;
            // 查找该数字在第一个字符串是否出现过
            auto it = pos.find(guess[i]);
            // 若没有出现过，或代表该位置的个数为0则跳过
            if(it == pos.end() || it->second <= 0)
                continue;
            // 否则找到该数字，将代表该数字的个数减一，使cow加一
            --(it->second);
            ++cow;
        }
        // 将bull和cow表示为要求格式，并返回结果
        string res = to_string(bull) + "A" + to_string(cow) + "B";
        return res;
    }
    
private:
    map<int, int> pos;
};