Try   HackMD

【LeetCode】 299. Bulls and Cows

Description

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.

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

你跟你朋友在玩一個公牛母牛的遊戲:你寫下一個數字並問你朋友他要猜的數字。每次你朋友猜測,你都要給一個提示他猜對了多少個數字在正確的位置(稱為公牛)和他猜對了多少數字但是位置是錯的(稱為母牛)。你的朋友必須不停的根據猜測結果來得到最後的答案。

請寫一個function會根據答案和猜測來回傳正確的提示,使用A代表公牛使用B代表母牛。

請記住答案或猜測可能包含重複的數字。

提示:你可以假設答案和猜測只會包含數字並且它們長度一樣。

Example:

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.

Solution

  • 題目這麼長,其實就是猜幾A幾B的遊戲。
  • 反正題目沒有限制時間或空間複雜度,我們就慢慢做即可。
  • 先跑一次檢查A(數字對位置對),如果一樣計數器就加一並移除該數字。
    • 不一樣就用一個hash記錄在該數字出現次數。
  • 跑完A之後就再跑一次,根據第一次的Hash去檢查,計算出B。

Code

class Solution { public: string getHint(string secret, string guess) { int A = 0, B = 0; map<char, int> count; //A for(int i = secret.size() - 1; i >= 0; i--) { if(secret[i] == guess[i]) { A++; secret.erase(secret.begin() + i); guess.erase(guess.begin() + i); } else if(count.count(secret[i])) count[secret[i]]++; else count[secret[i]] = 1; } //B for(int i = 0; i < guess.size(); i++) { if(count[guess[i]]) { count[guess[i]]--; B++; } } return to_string(A) + "A" + to_string(B) + "B"; } };
tags: LeetCode C++