LeetCode 75 Level 1 - Day 13 Hashmap

299. Bulls and Cows

• 題目連結
• 難易度：Medium

題目敘述

You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

• The number of "bulls", which are digits in the guess that are in the correct position.
• The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number $secret$ and your friend's guess $guess$, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where $x$ is the number of bulls and y is the number of cows. Note that both $secret$ and $guess$ may contain duplicate digits.

預設函數

char * getHint(char * secret, char * guess){

}

題目限制

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret and guess consist of digits only.

解題過程及程式碼

本題就是我們小時候玩過的猜數字，也就是1A2B遊戲，我們寫的程式要扮演知道答案的一方，題目會給我們 secret (正確答案) 及 guess (對方的猜測)，我們要回傳對方以 XAYB 形式呈現。其中X表示位置正確的數的個數，而Y表示數字正確而位置不對的數的個數。

解題想法是計算 secret 和 guess 的數字(0-9)出現個數，如果1個數字(0-9)在 secret 和 guess 都有出現，則有猜對。

• 在計算總共猜對的數字以 secret 和 guess 少的那邊為主。

  • 例如secret(1807)和guess(7781)對7來說只有猜中1個 (計算少的那邊secret只有1個7)，全部是3B。
  • 例如secret(1877)和guess(7081)對7來說還是只有猜中1個 (計算少的那邊guess只有1個7)，全部是3B。

• 把0-9的每個數量取secret和guess少的全部加起來就是總共猜對的數字。

• 再來一對一比對是否有猜中，可求得 A (位置及數字都對?)，最後計算B = 總共猜對的數字 - A的數量。

• 因為最後回傳是 XAYB 形式的字串，所以複習一下C語言中將整數轉為字串的方法。

  • How to convert an int to string in C?
  • 如何在 C 語言中把整數轉換成字串
  • sprintf()
  • itoa()

• 程式碼上傳

char output[50];

char * getHint(char * secret, char * guess){
    int secret_len = strlen(secret);
    int secret_num[10] = {0};
    int guess_num[10] = {0};
    int i, j, a_output, b_output, a_cal, b_cal;
    char temp[10];

    /* 計算secret和guess每個數字出現的次數，順便計算A */
    a_output = 0;
    for (int i=0; i<secret_len; i++) {
        secret_num[secret[i] - '0'] += 1;
        guess_num[guess[i] - '0'] += 1;
        if (secret[i] == guess[i]) {
            a_output++;
        }
    }

    /* 計算B */
    b_output = 0;
    for (int i=0; i<10; i++) {
        if ((secret_num[i] != 0) && (guess_num[i] != 0)) {
            if (secret_num[i] <= guess_num[i]) {
                b_output += secret_num[i];
            } else {
                b_output += guess_num[i];
            }

        }
    }
    b_output = b_output - a_output;

    strcpy(output, "");
    strcpy(temp, "");

    /* 將A整數轉為字串: int -> char[] */
    if (a_output != 0) {
        a_cal = a_output;
        i = 0;
        while (a_cal != 0) {
            a_cal = a_cal / 10;
            i++;
        }
        temp[i] = '\0';

        while (i > 0) {
            temp[i - 1] = (a_output % 10) + '0';
            a_output = a_output / 10;
            i--;
        }
    } else {
        temp[0] = '0';
        temp[1] = '\0';
    }

    strcpy(output, temp);
    strcat(output, "A");

    /* 將B整數轉為字串: int -> char[] */
    if (b_output != 0) {
        b_cal = b_output;
        i = 0;
        while (b_cal != 0) {
            b_cal = b_cal / 10;
            i++;
        }
        temp[i] = '\0';

        while (i > 0) {
            temp[i - 1] = (b_output % 10) + '0';
            b_output = b_output / 10;
            i--;
        }
    } else {
        temp[0] = '0';
        temp[1] = '\0';
    }

    strcat(output, temp);
    strcat(output, "B");

    return output;
}

今天就到這邊，謝謝大家!