转自我的 blog: 用 Swift 刷 Leetcode No.292 - Nim Game
继续按照难易度刷 LeetCode,这次的题目是 Nim Game(前面三个需要付费才能解锁……),看题目的提交者,好像还是个华人。
看完题目,第一感觉是这种数字推理的题目需要动态规划才能解决,但是都用上动态规划了也不可能是个 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 了。据我的个人经验,第一次递交是不可能通过的,果不其然,败在了一个大数上:
难道这个数字有什么特殊的吗?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的变种。