ACCESS用 斯威夫特 刷 Leetcode No.292 – Nim Game

转自我的 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)。正好后天读完了喵神的「斯威夫特er」,立刻想到了那只怕是因为递归爆栈了,但自我尝试了用定义内部函数也未果。

最好实际无法了,看了那道题的
Discuss,不看不掌握啊,原来那道题的没错解法唯有一句代码。许四人和自家同一,也是想使用递归来解题,而且不管怎么语言只借使用递归的都败在了1348820612以此数字上。再看各个one-line-solution,正像有的人说的那样,那并不是一道算法题,而是一个数学题(wiki),在此间提供一个别的blog的参考

毋庸置疑解法是:

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

而任何能够通过的解法,都是判定是不是能整除4的变种。

相关文章