299. Bulls and Cows299. 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.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.299. Bulls and Cows

类似猜数字问题。假设秘密数字是”1807″，对方猜了一个数字是”7810″，问猜对了多少位，又有多少位是没猜对，但是秘密数字中出现了。比如这里猜对了第2位，都是’8’；’7’、’1’和’0’虽然没猜对位置，但是秘密数字中也有’1’、’0’和’7’，所以算完全猜对了1个数位，猜对了3个数，但位置不对，输出”1A3B”。 简单题，先对秘密数字建立数字和频率的hash表，然后遍历猜测数字，如果对应位相等，则完全猜对一个；如果对应位不相等，但是在秘密数字的hash表中，且频率大于0，则猜对第二类。 完整代码如下：

class Solution {
public:
    string getHint(string secret, string guess)
    {
        unordered_map<char, int> uci;
        for (const auto& c : secret)
            ++uci[c];
        int a = 0, b = 0;
        for (int i = 0; i < guess.size(); ++i) {
            if (guess[i] == secret[i]) {
                ++a;
                –uci[secret[i]];
            }
        }
        for (int i = 0; i < guess.size(); ++i) {
            if (guess[i] != secret[i] && uci[guess[i]] > 0) {
                ++b;
                –uci[guess[i]];
            }
        }
        return to_string(a) + "A" + to_string(b) + "B";
    }
};

本代码提交AC，用时6MS。需要注意的是，两类数字的判断需要分开，只有先判断了对应位数字完全一样的数位，才判断第二类位置不对但数对的情况。比如

Secret number:  "1122"
Friend's guess: "1222"

如果混在一起判断的话，对于guess中的第一个2，Secret是1，但Secret中有2，所以这个2被分类为位置错，但数字对的情况，从而Secret中的2的频率减少为1，导致最后一个2，虽然数字和位置完全一样，但是Secret中2的频率已经是0了，无法判断为A类。所以需要完全判断完A类之后，才判断B类。

二刷。因为只有0-9这10个数字，可以用数组代替hash：

class Solution {
public:
	string getHint(string secret, string guess) {
		int n = secret.size();
		int a = 0, b = 0;
		vector<int> s(10, 0), g(10, 0);
		for (int i = 0; i < n; ++i) {
			if (secret[i] == guess[i])++a;
			else {
				++s[secret[i] - '0'];
				++g[guess[i] - '0'];
			}
		}
		for (int i = 0; i < 10; ++i) {
			b += min(s[i], g[i]);
		}
		return to_string(a) + "A" + to_string(b) + "B";
	}
};

本代码提交AC，用时4MS。

LeetCode Longest Harmonious Subsequence We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1. Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences. Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].