leedcode题集:299. Bulls and Cows
第三天:299. Bulls and Cows
题目大意就是两个字符串,一个秘密字符串,一个猜测字符串,然后比较这两个字符串。如果数字和位置都对应上,则是A类型;如果只是数字对上,位置对不上,则是B类型,问AB类型各有多少。如果重复的是一对多,则只算一个。
题目分析:A类型好求,就是一个循环完事儿了。B类型需要比较两个字符串中相同数字的个数,考虑到每一位都是数字,即数字类型是有限个数,即0-9,故而开一个数组,则可记录每个字符串中对应数字的个数。两个字符串对应两个数组,两个数组中对应位置的数值之差绝对值则是该数字的“落单数”,10个数字之和,即是我们所求的最终“落单数”。
则B类型个数=(两个字符串长度-落单数-A类型*2)/2。完整代码如下:
class Solution {
public:
string getHint(string secret, string guess) {
int numsetA[10] = {0};
int numsetB[10] = {0};
int bullNum = 0;
int len = secret.size();
for(int i=0;i<len;i++){
if(secret[i] == guess[i]){
bullNum++;
} else {
int temNum = secret[i] - '0';
numsetA[temNum]++;
temNum = guess[i] - '0';
numsetB[temNum]++;
}
}
int setSize = 0;
for(int i=0;i<10;i++){
int count = abs(numsetA[i] - numsetB[i]);
setSize+=count;
}
// cout <<setSize <<endl;
int cowNum = (2*len - setSize - 2*bullNum)/2;
stringstream ss;
ss <<bullNum <<"A" <<cowNum <<"B";
string res = "";
ss >> res;
return res;
}
};