leetcode筆記：Bulls and Cows

leetcode筆記：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.

For example:

Secret number: “1807”
Friend’s guess: “7810”
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
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. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number: “1123”
Friend’s guess: “0111”
In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.
You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

二. 題目分析

該題即是猜數字（又稱 Bulls and Cows ）是一種大概於20世紀中期興起於英國的益智類小游戲。游戲規則抄送：

在掃描過程前，創建一個數組用於記錄0~9字符出現的次數，並在掃描時使用兩種規則：

一個例子：當temp中’1’所對應的下標元素小於零時，此時說明guess此前出現過’1’的次數比secret多（或者說沒有被secret出現’1’的次數抵消完），此時若secret出現’1’，則B++；反之，當temp中’1’所對應的下標元素大於零時，此時說明secret此前出現過’1’的次數比guess多（或者說沒有被guess出現’1’的次數抵消完），此時若guess出現’1’，則B++。

三. 示例代碼

class Solution {
public:
    string getHint(string secret, string guess) {
        int temp[10] = {0}; // 用於存放0~9字符出現的次數
        int SIZE = secret.size();
        int A = 0, B = 0;
        for (int i = 0; i < SIZE; ++i)
        {
            if (secret[i] == guess[i])
            {
                ++A;
                continue;
            }
            else // 若字符在secret中出現一次則+1，在guess中出現一次則-1
            {
                if (temp[secret[i] - '0'] < 0)
                    ++B;
                ++temp[secret[i] - '0'];

                if (temp[guess[i] - '0'] > 0)
                    ++B;
                --temp[guess[i] - '0'];
            }
        }
        char result[10] = {0};  
        sprintf(result, "%dA%dB", A, B);
        return result;
    }
};

四. 小結

該題雖然比較簡單，但還是挺有意思的，最後輸出xAxB也改了一小段時間。