iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 29
1
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 29

【從面試題學邏輯-29】如何寫出1A2B猜數字遊戲?(leetcode 299. Bulls and Cows)

題目:
請寫一個猜數字的方法,就是我們常玩的1A2B

舉例:
假設答案為1234,猜1043,應該會拿到1A2B

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


終於30天鐵人賽要迎來結尾了,一直在想到底最後要用什麼題目,才最具有代表性,又貼近這個主題呢?/images/emoticon/emoticon23.gif

後來想到了1A2B這個東西,這應該是程式設計師最早會碰到的題目吧?那大家還記得最剛開始我們用陣列存是否出現的作法呢?

這一題剛好就是兩者的綜合,我們就回頭看看最一開始學到的東西,以及大家在新手時期碰到的東西吧

我們會需要2個int,分別是cows和bulls,分別幫我們存A和B的數量
以及一條0~9的int陣列,幫我們處理B的狀態

int bulls=0,cows=0;
int[] nums = new int[10];

所以先得出上面的程式碼

在來我們要逐一讀過secret和guess的字,所以要有個迴圈

for(int i=0;i<secret.length();i++){
    // blah blah
}

由於會同時讀取兩個String,所以只要一個迴圈就夠了

再來,如果兩個String在同地方的數字一樣,我們就加一個A

if(secret.charAt(i)==guess.charAt(i)) {
    bulls++;
}

不難理解吧?

接下來是B的部分,B要怎麼做到同步處理呢?這時就要用到剛剛開的陣列了
解答的數字如果沒有在正確位置對到回答,我們就在陣列的第i個位置加1,第i個位置就是解答數字(比如說解答是5,沒有對應到回答的話,就把nums[5]加1)

反之,如果是回答沒有對應到解答,我們就在第i個位置減1

這是什麼意思呢?如果是正數,代表解答有一個數出現,但在那個位置沒有對到回答,等著別人和它配對。如果是負數,代表回答沒有對到解答,等看看有沒有解答能配對它

假設解答讀到4,而對面的位置不是4時,就到陣列看看存4的地方,是不是前面有人等著配對,是的話我們就把B加1

反之亦然,這樣子我們就能算出B來了

由此我們可以得出這段程式碼:

} else {
    if(nums[secret.charAt(i)-'0']++<0) cows++;
    if(nums[guess.charAt(i)-'0']-->0) cows++;
}

注意一下:

  1. -'0'就是運用ASCII的計算,減完之後就會拿到對應數字的int
  2. i++就是整段程式碼跑完後,再把i加1,所以就算沒有符合if,都會把nums做加減的動作(i--相同)

上面那段程式碼也等於下面這段(純粹就是省打字功夫):

if(nums[secret.charAt(i)-'0']<0) cows++;
if(nums[guess.charAt(i)-'0']>0) cows++;
nums[secret.charAt(i)-'0']++;
nums[guess.charAt(i)-'0']--;

我們最後把上面的程式碼全部組合起來就能得到下面的東西:

class Solution {
    public String getHint(String secret, String guess) {
        int bulls=0,cows=0;
        int[] nums = new int[10];
        for(int i=0;i<secret.length();i++) {
            if(secret.charAt(i)==guess.charAt(i)) {
                bulls++;
            } else {
                if(nums[secret.charAt(i)-'0']++<0) cows++;
                if(nums[guess.charAt(i)-'0']-->0) cows++;
            }
        }
        return bulls+"A"+cows+"B";
    }
}

上一篇
【從面試題學邏輯-28】路面坑洞坑坑巴巴兼積大水(leetcode 42. Trapping Rain Water)
下一篇
30天解題完結,回顧解了什麼
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言