题目描述

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.

For example, 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.

解法一

思路

这题实际上是一个有趣的数学题,在说答案前还是先想想思考过程:

  • 题目描述里已经提示了,谁碰到还剩1、2或3颗石子的时候就一定会赢,因为肯定会一口气拿完。
  • 现在考虑还剩4颗石子的时候,这时自己最少要拿1颗,最多能拿3颗,这样留给对手的一定是[1, 3]颗石子,这样对手一定赢。
  • 再来考虑还剩5颗的时候,留给对手的可以是[2, 4]颗石子,显然只能是留4颗石子给对手才能确保自己赢;剩6颗、7颗也是一样的道理。
  • 再看剩8颗的情况,与[5, 7]颗不同的是,现在留给对手的只能是[5, 7],而根据上一步的分析这样对手一定赢。

综上,因为自己走第一步,所以当初始的石子数为4的倍数时,自己肯定输;当不为4的倍数时,自己肯定赢。因为如果是4的倍数,则对手会一直让自己剩的石子数为4的倍数,直到最终对手拿完所有石子;类似地,如果不是4的倍数,则自己会让对手一直剩的石子数为4的倍数,直到最终自己拿完所有石子。

Python

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

Java

public class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

C++

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};