LeetCode筆記:299. Bulls and Cows

問(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


查看作者首頁(yè)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末涛贯,一起剝皮案震驚了整個(gè)濱河市诽嘉,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌弟翘,老刑警劉巖虫腋,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異稀余,居然都是意外死亡悦冀,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)睛琳,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)雏门,“玉大人嘿歌,你說(shuō)我怎么就攤上這事∽掠埃” “怎么了宙帝?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)募闲。 經(jīng)常有香客問(wèn)我步脓,道長(zhǎng),這世上最難降的妖魔是什么浩螺? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任靴患,我火速辦了婚禮,結(jié)果婚禮上要出,老公的妹妹穿的比我還像新娘鸳君。我一直安慰自己,他們只是感情好患蹂,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布或颊。 她就那樣靜靜地躺著,像睡著了一般传于。 火紅的嫁衣襯著肌膚如雪囱挑。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1 312
  • 那天沼溜,我揣著相機(jī)與錄音平挑,去河邊找鬼。 笑死系草,一個(gè)胖子當(dāng)著我的面吹牛通熄,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播找都,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼棠隐,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了檐嚣?” 一聲冷哼從身側(cè)響起助泽,我...
    開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎嚎京,沒(méi)想到半個(gè)月后嗡贺,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡鞍帝,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年诫睬,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片帕涌。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡摄凡,死狀恐怖续徽,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情亲澡,我是刑警寧澤钦扭,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站床绪,受9級(jí)特大地震影響客情,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜癞己,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一膀斋、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧痹雅,春花似錦仰担、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至铃将,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間哑梳,已是汗流浹背劲阎。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留哟楷,地道東北人体啰。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓捞烟,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親锡垄。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容