轉(zhuǎn)自我的 blog: 用 Swift 刷 Leetcode No.292 - Nim Game

繼續(xù)按照難易度刷 LeetCode，這次的題目是 Nim Game（前面三個(gè)需要付費(fèi)才能解鎖……），看題目的提交者，好像還是個(gè)華人。

leetcode_292.png

看完題目，第一感覺(jué)是這種數(shù)字推理的題目需要?jiǎng)討B(tài)規(guī)劃才能解決，但是都用上動(dòng)態(tài)規(guī)劃了也不可能是個(gè) Easy 的題目啊。再想一下就想出解決方法了，靠遞歸嘛，根據(jù) n-1 來(lái)求解 n。

class Solution {
    var round = 1
    func canWinNim(n: Int) -> Bool {
        if n < 4 {
            if round%2 == 1{
                return true
            } else {
                return false
            }
        } else {
            round += 1
            return canWinNim(n-1) || canWinNim(n-2) || canWinNim(n-3)
        }
    }
}

試了幾個(gè) case，都沒(méi)問(wèn)題，就猛擊 Submit Solution 了。據(jù)我的個(gè)人經(jīng)驗(yàn)，第一次遞交是不可能通過(guò)的，果不其然，敗在了一個(gè)大數(shù)上：

error.png

難道這個(gè)數(shù)字有什么特殊的嗎？1348820612這個(gè)數(shù)字并沒(méi)有超過(guò) Int32.max 啊。我在 Playground 中執(zhí)行這個(gè)數(shù)字的 case，果然也沒(méi)有執(zhí)行成功，得到了 error: Playground execution aborted: Execution was interrupted, reason: EXC_BAD_ACCESS (code=2, address=0x7fff5ea0df98)。正好今天讀完了喵神的「Swifter」，立刻想到了這可能是因?yàn)檫f歸爆棧了，但我嘗試了用定義內(nèi)部函數(shù)也未果。

最好實(shí)在沒(méi)辦法了，看了這道題的 Discuss，不看不知道啊，原來(lái)這道題的正確解法只有一句代碼。許多人和我一樣，也是想利用遞歸來(lái)解題，而且無(wú)論什么語(yǔ)言只要是用遞歸的都敗在了1348820612這個(gè)數(shù)字上。再看各種 one-line-solution，正像有的人說(shuō)的那樣，這并不是一道算法題，而是一個(gè)數(shù)學(xué)題（wiki），在這里提供一個(gè)其他blog的參考。

正確解法是：

class Solution {
    func canWinNim(n: Int) -> Bool {
        return n%4 != 0
    }
}

而其他可以通過(guò)的解法，都是判斷是否能整除4的變種。