題目

難度：★★☆☆☆
類型：數(shù)學(xué)

你和你的朋友，兩個(gè)人一起玩 Nim 游戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。

你們是聰明人，每一步都是最優(yōu)解。 編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。

示例

輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭，那么你永遠(yuǎn)不會(huì)贏得比賽；
因?yàn)闊o論你拿走 1 塊、2 塊 還是 3 塊石頭，最后一塊石頭總是會(huì)被你的朋友拿走。

解答

這是道有趣的智力題。我們首先考慮什么情況下能贏，從示例可以看到，當(dāng)只剩下4塊石頭時(shí)，輪到誰拿誰輸，因?yàn)榱硪粋€(gè)人總是可以把剩下的石頭全部拿完。

那么勝利目標(biāo)就成為希望自己拿走石頭后保證還剩4塊石頭，怎樣才能做到呢？同樣的道理，只需要還剩8塊石頭的時(shí)候輪到了對(duì)方拿，那么不管對(duì)方拿多少，1個(gè)2個(gè)或者3個(gè)，自己拿的時(shí)候都可以保證只剩4塊石頭，那怎么保證還剩8塊石頭的時(shí)候輪到了對(duì)方拿呢……

綜上，我們可以得出，只要我們能夠保證自己這輪拿走石頭后，剩余的石頭個(gè)數(shù)是4的整數(shù)倍，這時(shí)輪到誰拿誰輸，就可以逼死隊(duì)友，這樣問題就很簡(jiǎn)單，如果給定的石頭個(gè)數(shù)不是4的整數(shù)倍，那么這種情況就穩(wěn)勝，否則就會(huì)輸（如果隊(duì)友掌握了以上技巧的話）。

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

如有疑問或建議，歡迎評(píng)論區(qū)留言~