292. Nim 游戏

Easy

题目描述

你和你的朋友正在玩以下的 Nim 游戏：

• 桌子上有一堆石头。
• 你和你的朋友轮流进行，你先开始。
• 每一回合，轮到的人拿掉 1 到 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你和你的朋友都会玩得最优，给定桌子上石头的数量 n，如果你能获胜返回 true，否则返回 false。

示例 1：

输入：n = 4
输出：false
解释：以下是可能的结果：
1. 你拿掉 1 块石头。你的朋友拿掉 3 块石头，包括最后一块。你的朋友获胜。
2. 你拿掉 2 块石头。你的朋友拿掉 2 块石头，包括最后一块。你的朋友获胜。
3. 你拿掉 3 块石头。你的朋友拿掉最后一块石头。你的朋友获胜。
在所有结果中，你的朋友都获胜。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

约束条件：

• 1 <= n <= 2^31 - 1

提示：

• 如果堆中有 5 块石头，你能找出一种拿石头的方法使你总是获胜者吗？

解题思路

这是一个经典的博弈论问题，可以通过数学规律来解决。

让我们分析一下不同石头数量的情况：

• n = 1, 2, 3：我可以一次性拿完所有石头，必胜
• n = 4：无论我拿 1, 2, 3 块，剩余的石头数都在 1-3 之间，对手可以一次拿完，我必败
• n = 5, 6, 7：我可以拿掉一些石头，让剩余石头数为 4，这样对手就处于必败状态
• n = 8：无论我拿多少块（1-3），剩余石头数都在 5-7 之间，对手又能让我处于必败状态

通过观察可以发现规律：当石头数量是 4 的倍数时，先手必败；否则先手必胜。

这是因为：

1. 如果 n 不是 4 的倍数，我可以拿掉适当数量的石头（使剩余石头数为 4 的倍数），让对手处于必败状态
2. 如果 n 是 4 的倍数，无论我拿掉多少石头，剩余数量都不会是 4 的倍数，对手总能通过合适的策略让我再次面对 4 的倍数

因此，解法就是简单地判断 n 是否不是 4 的倍数。

代码实现

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

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

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

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return n % 4 !== 0;
};

复杂度分析

相关题目

• . Flip Game II (Medium)