問(wèn)題：
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.
大意：
你和你的朋友玩下面這個(gè)Bulls and Cows的游戲：你寫(xiě)一個(gè)數(shù)字怖现，然后問(wèn)你的朋友去猜數(shù)字。每次你的朋友進(jìn)行一次猜測(cè)玉罐，你都給他提示說(shuō)有多少數(shù)字是數(shù)字與位置都正確的（成為bulls）以及多少數(shù)字是數(shù)字有但是位置不正確的（成為cows）屈嗤。你的朋友會(huì)根據(jù)提示最終猜出數(shù)字來(lái)。
例子：秘密數(shù)字：“1807”
朋友的猜測(cè)：“7810”提示：1個(gè)bull以及3個(gè)cows吊输。（bull是8饶号，cows是0，1和7）
寫(xiě)一個(gè)函數(shù)來(lái)根據(jù)秘密數(shù)字和朋友的額猜測(cè)來(lái)返回暗示季蚂，使用A表示bull茫船，B表示cows。在上面的例子中扭屁，你的函數(shù)應(yīng)該返回“1A3B”算谈。
請(qǐng)注意秘密數(shù)字和朋友的猜測(cè)都可能包含重復(fù)的數(shù)字，比如：秘密數(shù)字：“1123”
朋友的猜測(cè)：“0111”這種情況下料滥，朋友猜測(cè)中的第一個(gè)1是bull濒生，第二和第三個(gè)1是cow，你的函數(shù)應(yīng)該返回“1A1B”幔欧。
你可以假設(shè)秘密數(shù)字和朋友的猜測(cè)都只包含數(shù)字罪治，并且長(zhǎng)度相等。
思路：
這道題分兩步：
第一步找到bull礁蔗，也就是數(shù)字和位置都正確的個(gè)數(shù)觉义，這個(gè)直接循環(huán)比對(duì)兩個(gè)字符串同等位置的數(shù)字是否一樣就好，為了方便我們先全部轉(zhuǎn)換成數(shù)組去比較浴井，比較完了記錄下個(gè)數(shù)晒骇，還要記錄下有哪些位置的數(shù)字是bull，這樣第二步找cow的時(shí)候就不要再判斷了磺浙。
第二步找cow洪囤，再次循環(huán)朋友的猜測(cè)，這次我們要跳過(guò)那些是bull的位置撕氧，對(duì)不是bull的每一個(gè)數(shù)字瘤缩，去循環(huán)秘密數(shù)字中的數(shù)進(jìn)行判斷，判斷時(shí)要注意第一不能位置一樣伦泥，第二數(shù)字要相等剥啤，第三不能是秘密數(shù)字中已經(jīng)是bull的位置锦溪。且找到以后除了增加cow數(shù)字外也要記錄下來(lái)在秘密數(shù)字中的位置，以后就不要再找了府怯。
在第二次找的過(guò)程中要注意我們不能重復(fù)找秘密數(shù)字中的位置刻诊，也就是有一個(gè)新數(shù)組要記錄秘密數(shù)字中已經(jīng)被找到的數(shù)字，這時(shí)候和bull中的位置是不一樣的牺丙，所以要另外加一個(gè)數(shù)組则涯，但是加的時(shí)候不能直接等于之前第一步記錄的數(shù)組來(lái)創(chuàng)建，這樣在進(jìn)行修改數(shù)組的時(shí)候其實(shí)還是修改的第一個(gè)數(shù)組冲簿，因?yàn)橹皇且昧艘槐槲恢檬钦M(jìn)行深復(fù)制，使用clone民假。
此外對(duì)于朋友猜測(cè)中的一個(gè)數(shù)組，只能找一個(gè)cow龙优，不能循環(huán)找多個(gè)羊异，所以找到一個(gè)以后直接break退出循環(huán)開(kāi)始找下一個(gè)數(shù)字。
代碼（Java）：
public class Solution {
public String getHint(String secret, String guess) {
char[] secretArr = secret.toCharArray();
char[] guessArr = guess.toCharArray();
int[] bullArr = new int[guess.length()];
int bull = 0;
int cow = 0;
for (int i = 0; i < guessArr.length; i++) {
if (guessArr[i] == secretArr[i]) {
bull ++;
bullArr[i] = 1;
}
}
int[] bullSecretArr = bullArr.clone();
for (int i = 0; i < guessArr.length; i++) {
if (bullArr[i] == 0) {
for (int j = 0; j < secretArr.length; j++) {
if (i != j && guessArr[i] == secretArr[j] && bullSecretArr[j] == 0) {
cow++;
bullSecretArr[j] = 1;
break;
}
}
}
}
String result = String.valueOf(bull) + 'A' + String.valueOf(cow) + 'B';
return result;
}
}
他山之石：
public class Solution {
public String getHint(String secret, String guess) {
int[] a1 = new int[256];
int[] a2 = new int[256];
int count1 = 0, count2 = 0;
for(int i = 0; i < secret.length(); i++){
if(secret.charAt(i) == guess.charAt(i)) count1++;
else{
a1[secret.charAt(i)]++;
a2[guess.charAt(i)]++;
}
}
for(int i = 0; i < 255; i++){
if(a1[i] == a2[i]) count2+=a1[i];
else count2 += Math.min(a1[i],a2[i]);
}
return count1+"A"+count2+"B";
}
}
這個(gè)做法第一步也是直接找bull彤断，巧妙的地方在于第二步找cow數(shù)量的方法野舶。在第一步中對(duì)于不是bull的位置的數(shù)字，分別都記錄下來(lái)對(duì)應(yīng)位置的數(shù)字宰衙，對(duì)數(shù)字的數(shù)量進(jìn)行累加平道，這樣循環(huán)一遍后就知道各自還有哪些數(shù)字沒(méi)找到，以及他們的個(gè)數(shù)供炼。在找cow的時(shí)候一屋，只需要對(duì)每個(gè)出現(xiàn)過(guò)的數(shù)字，取兩邊出現(xiàn)的較少的那一個(gè)數(shù)量即可袋哼，這樣也可以避免重復(fù)冀墨，很巧妙地減少了時(shí)間復(fù)雜度。
合集：https://github.com/Cloudox/LeetCode-Record
