江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第292题：Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏： - 桌子上有一堆石头。 - 你们轮流进行自己的回合，你作为先手。 - 每一回合，轮到的人可以拿掉 1 - 3 块石头。 - 拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false。

📖 文章摘要

本文详细解析LeetCode第292题“Nim 游戏”，这是一道考察数学规律和博弈论的简单难度题目。文章提供了数学分析和动态规划两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习数学规律和博弈论的读者。

核心知识点： 数学规律、博弈论、动态规划
难度等级： 简单
推荐人群： 具备基础算法知识，想要提升数学思维和博弈论能力的开发者

题目描述

你和你的朋友，两个人一起玩 Nim 游戏：

  • 桌子上有一堆石头。
  • 你们轮流进行自己的回合，你作为先手。
  • 每一回合，轮到的人可以拿掉 1 - 3 块石头。
  • 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false。

示例

示例 1：

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

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示

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

解题思路

本题可以使用两种方法来实现：

  1. 数学分析：

    • 观察规律发现，当n是4的倍数时，先手必输
    • 否则，先手可以通过拿取适当数量的石头，使对手面对4的倍数
    • 因此，只需要判断n是否能被4整除

  2. 动态规划：

    • 定义dp[i]表示面对i个石头时是否能赢
    • 如果存在一种拿法使得对手必输，则当前状态必赢
    • 否则当前状态必输
    • 由于n可能很大，需要优化空间复杂度

图解思路

数学规律分析表

石头数量 先手选择 对手选择 结果
1 拿1 - 赢
2 拿2 - 赢
3 拿3 - 赢
4 拿1/2/3 拿3/2/1 输
5 拿1 对手面对4 赢
6 拿2 对手面对4 赢
7 拿3 对手面对4 赢
8 拿1/2/3 对手面对7/6/5 输

状态转换表

状态 操作 结果
n % 4 == 0 任意选择 必输
n % 4 != 0 选择(n % 4) 必赢

代码实现

C# 实现

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

Python 实现

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

C++ 实现

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

执行结果

C# 实现

  • 执行用时：36 ms
  • 内存消耗：14.8 MB

Python 实现

  • 执行用时：32 ms
  • 内存消耗：14.2 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.9 MB

性能对比

语言 执行用时 内存消耗 特点
C# 36 ms 14.8 MB 代码结构清晰，性能适中
Python 32 ms 14.2 MB 代码最简洁，性能不错
C++ 0 ms 5.9 MB 性能最优，内存占用最小

代码亮点

  1. 🎯 使用数学规律简化问题
  2. 💡 一行代码解决问题
  3. 🔍 时间复杂度O(1)
  4. 🎨 代码简洁明了

常见错误分析

  1. 🚫 未发现4的倍数规律
  2. 🚫 使用动态规划导致超时
  3. 🚫 未考虑大数情况
  4. 🚫 实现过于复杂

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
数学分析 O(1) O(1) 最优解 需要数学思维
动态规划 O(n) O(n) 直观 空间复杂度高

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第292题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！