299.BullsandCows

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进行比较，保证A和B的长度相等。

bull:相应下标下字符相等，bull++

cow:字符串B和字符串A中字符相同但下标不同的个数。

用数组和unordered_map table记录字符c出现的次数

方法一：扫描两次

第一次：计算bull，扫描A，B

第二次：计算cow，扫描B

方法二：扫描一次

在扫描过程中，假定第i个下标时，A的字符为ca，B的字符为cb，在扫描过程中，table[ca]++,table[cb]--;

情况1：table[ca]==table[cb]  则bull++;

情况2：

a)table[ca]<0,则说明当前字符ca在扫描[0——i-1]的下标时，在字符串B中出现过（table[cb]--，因对字符串B中的cb执行的是减一操作)，这种情况处理的是，字符c在串A的出现时间比串B出现的晚。

b)table[cb]>0,则说明当前字符cb在扫描[0——i-1]的下标时，在字符串A中出现过(table[ca]++,因对字符串A中的ca执行加一操作)，这种情况处理的是，字符c在串A的出现时间比串B出现的早。

对a,b两种情况均要判断。在判断完 a,b后，要执行相应的--和++操作，

    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 table;
        int table[10]={0};
        /*for(int i=0;i0){
                --table[guess[i]];
                numb++;
            }
        }*/
        for(int i=0;i0)
                    numb++;
                //table[secret[i]]++;
                //table[guess[i]]--;
            }
        }
        //cout<
return to_string(numa)+"A"+to_string(numb)+"B" 减少了一次字符串构建和拷贝过程。可以利用RVO，
用数组比unordered_map<>更减少时间开销，从12ms减小到4ms，
            
            
                        

            当前标题：299.BullsandCows            

            转载注明：http://cxhlcq.com/article/jdegoe.html