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.
来源: https://leetcode.com/problems/bulls-and-cows/
题目大意:给定两个string变量a和b,bulls表示a和b相同位上有相同数的个数,cows表示a和b不同位上有相同数的个数。注意计算过的不能再算。
解题思路:分为两类来计算,如1807和7810
(1)相同位上有相同数(8,8)
直接统计这样的位数即可
(2)相同位上有不同数(107和710)
先统计每个数出现
具体思路见代码注释:
class Solution { public: string getHint(string secret, string guess) { int hash[10] = {0};//0~9在secret出现的次数 int len = secret.length(); int countA = 0 ,countB=0; int *isFind = new int[len];//统计那些位上的数相同 memset(isFind,0,len*sizeof(int)); for(int i =0 ; i < len ;i++) { if(secret[i]==guess[i]){//相同位上有相同数 isFind[i] = 1; countA++; } else hash[secret[i]-'0']++;//如果相同位上数不相等就记录下来 } for(int i =0 ; i < len ;i++) { if(isFind[i]==0){//跳过相同位上有相同数 if(hash[guess[i]-'0']!=0)//如果出现过 { hash[guess[i]-'0']--;//次数减1 countB++; } } } string ret; stringstream ss; ss<>ret;//按特定格式输出 return ret; } };