转自我的 blog: 用 Swift 刷 Leetcode No.292 - Nim Game

继续按照难易度刷 LeetCode，这次的题目是 Nim Game（前面三个需要付费才能解锁……），看题目的提交者，好像还是个华人。

leetcode_292.png

看完题目，第一感觉是这种数字推理的题目需要动态规划才能解决，但是都用上动态规划了也不可能是个 Easy 的题目啊。再想一下就想出解决方法了，靠递归嘛，根据 n-1 来求解 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)
        }
    }
}

试了几个 case，都没问题，就猛击 Submit Solution 了。据我的个人经验，第一次递交是不可能通过的，果不其然，败在了一个大数上：

error.png

难道这个数字有什么特殊的吗？1348820612这个数字并没有超过 Int32.max 啊。我在 Playground 中执行这个数字的 case，果然也没有执行成功，得到了 error: Playground execution aborted: Execution was interrupted, reason: EXC_BAD_ACCESS (code=2, address=0x7fff5ea0df98)。正好今天读完了喵神的「Swifter」，立刻想到了这可能是因为递归爆栈了，但我尝试了用定义内部函数也未果。

最好实在没办法了，看了这道题的 Discuss，不看不知道啊，原来这道题的正确解法只有一句代码。许多人和我一样，也是想利用递归来解题，而且无论什么语言只要是用递归的都败在了1348820612这个数字上。再看各种 one-line-solution，正像有的人说的那样，这并不是一道算法题，而是一个数学题（wiki），在这里提供一个其他blog的参考。

正确解法是：

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

而其他可以通过的解法，都是判断是否能整除4的变种。