故 Swift 刷 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)。正好今天读了了喵神的「Swifter」,立刻想到了当下也许是坐递归爆栈了,但自己尝试了所以定义内部函数也非果。

太好实际没办法了,看了立即道题之
Discuss,不扣不懂得呀,原来这道题之不错解法只发同一词代码。许多丁同自同,也是怀念采取递归来解题,而且不管什么语言只要是故递归的都散在了1348820612以此数字达到。再看各种
one-line-solution,正像有些人说的那样,这并无是千篇一律鸣算法题,而是一个数学题(wiki),在这边提供一个任何blog的参考。

科学解法是:

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

万一另外可以经过的解法,都是判定是否会整除4底变种。

相关文章