LeetCode 292. Nim Game

Description

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

Example:

Input: 4
Output: false 
Explanation: If there are 4 stones in the heap, then you will never win the game;
             No matter 1, 2, or 3 stones you remove, the last stone will always be 
             removed by your friend.

描述

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路

• 我先拿

1. 如果有1到3块是否，先拿的一定赢
2. 如果有4块先拿的一定输；
3. 如果有5个，我先拿1个，剩下四个，此时对手的情况和在有4快我先拿的情况一样，由于有4个先拿的一定输，所以对手一定输，所以我一定赢
4. 如果有6个，我先拿2个，此时剩下4个，在有4快的情况下先拿的一定输，所以对手一定输，所以我一定赢
5. 如果有7个，我先拿3个，此时剩下4个，在有4快的情况下先拿的一定输，所以对手一定输，所以我一定赢
6. 如果有8个，我先拿3个，此时剩下5个，有5块先拿的一定赢，我一定输；如果我先拿2快，此时剩6块，有6块先拿的一定赢，我一定输；如果我先拿1快，此时剩7块，有7块先拿的一定赢，我一定输；所以有8块我一定输
7. 如果有9块，我先拿1块，此时剩下8块，有8块先拿的一定输，所以我一定赢
8. 即每4块一个循环，前三个赢，最后一个输；
9. 我们对给定的数模上4，如果结果为0说明是4的倍数，一定输，否则一定赢

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-08 11:59:57
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-08 12:23:10
class Solution:
    def canWinNim(self, n: 'int') -> 'bool':
        # 如果是4的倍数，一定会失败
        if not n % 4: return False
        # 否则一定赢，返回True
        return True

源代码文件在这里.