299. Bulls and Cows

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.

題意：

字符串A與字符串B進(jìn)行比較，保證A和B的長度相等。

bull:相應(yīng)下標(biāo)下字符相等，bull++

cow:字符串B和字符串A中字符相同但下標(biāo)不同的個數(shù)。

用數(shù)組和unordered_map<char,int> table記錄字符c出現(xiàn)的次數(shù)

方法一：掃描兩次

第一次：計算bull，掃描A，B

第二次：計算cow，掃描B

方法二：掃描一次

在掃描過程中，假定第i個下標(biāo)時，A的字符為ca，B的字符為cb，在掃描過程中，table[ca]++,table[cb]--;

情況1：table[ca]==table[cb]  則bull++;

情況2：

a)table[ca]<0,則說明當(dāng)前字符ca在掃描[0——i-1]的下標(biāo)時，在字符串B中出現(xiàn)過（table[cb]--，因?qū)ψ址瓸中的cb執(zhí)行的是減一操作)，這種情況處理的是，字符c在串A的出現(xiàn)時間比串B出現(xiàn)的晚。

b)table[cb]>0,則說明當(dāng)前字符cb在掃描[0——i-1]的下標(biāo)時，在字符串A中出現(xiàn)過(table[ca]++,因?qū)ψ址瓵中的ca執(zhí)行加一操作)，這種情況處理的是，字符c在串A的出現(xiàn)時間比串B出現(xiàn)的早。

對a,b兩種情況均要判斷。在判斷完 a,b后，要執(zhí)行相應(yīng)的--和++操作，

    string getHint(string secret, string guess) {
        int len_s=secret.length(),len_g=guess.length();
        
        if(len_s==0)
            return "";
        int numa=0,numb=0;
        //unordered_map<char,int> table;
        int table[10]={0};
        /*for(int i=0;i<len_s;++i){
            if(secret[i]==guess[i]){
                numa++;
            }
            table[secret[i]]++;
        }
        
        for(int i=0;i<len_s;++i){
            if(table.find(guess[i])!=table.end()&&table[guess[i]]>0){
                --table[guess[i]];
                numb++;
            }
        }*/
        for(int i=0;i<len_s;++i){
            if(secret[i]==guess[i]){
                numa++;
            }
            else{
                if(table[secret[i]-'0']++<0)
                    numb++;
                if(table[guess[i]-'0']-->0)
                    numb++;
                //table[secret[i]]++;
                //table[guess[i]]--;
            }
        }
        //cout<<numa<<numb-numa;
        //string res=to_string(numa)+"A"+to_string(numb)+"B";
        return to_string(numa)+"A"+to_string(numb)+"B";
    }

return to_string(numa)+"A"+to_string(numb)+"B" 減少了一次字符串構(gòu)建和拷貝過程?？梢岳肦VO，
用數(shù)組比unordered_map<>更減少時間開銷，從12ms減小到4ms，