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.

公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站制作、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)公司推出定襄免費(fèi)做網(wǎng)站回饋大家。

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的長(zhǎng)度相等。

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

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

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

方法一：掃描兩次

第一次：計(jì)算bull，掃描A，B

第二次：計(jì)算cow，掃描B

方法二：掃描一次

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

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

情況2：

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

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

對(duì)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)建和拷貝過(guò)程?？梢岳肦VO，
用數(shù)組比unordered_map<>更減少時(shí)間開(kāi)銷，從12ms減小到4ms，

網(wǎng)站標(biāo)題：299.BullsandCows
網(wǎng)頁(yè)路徑：http://bm7419.com/article4/jdegoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、企業(yè)建站、微信公眾號(hào)、網(wǎng)站改版、靜態(tài)網(wǎng)站、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)