292.Nim 游戏

你和你的朋友，两个人一起玩 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

Related Topics

  • 脑筋急转弯
  • 数学
  • 博弈

题目链接: link

解答

本题的难度是 Easy.

这次这个题目其实是小时候玩的一个游戏的简化版，给定 n 个石头, 然后每次可以拿 1-k 个石头, 拿到最后石头的人获胜，这个游戏是可以一开始就知道结果的，如果 n 是 k+1 的倍数，那么先手的人一定会输，否则先手的人一定会赢。这个题目就是这个游戏的简化版，例如本题 k 确定是3.

每次可以拿1-3个石头，最后拿光石头的人获胜。如果石头的数量是4的倍数，那么先手的人一定会输。因为无论先手拿多少个石头，后手都可以拿到4-x个石头，使得剩下的石头的数量是4的倍数。所以只要石头的数量是4的倍数，那么先手的人一定会输。所以只要石头的数量不是4的倍数，那么先手的人一定会赢。所以只要判断石头的数量是不是4的倍数就可以了。所以代码其实非常简单.

代码如下:

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

这个题目的时间复杂度是 O(1), 空间复杂度是 O(1). 并且时间效率击败 100%. 看了一下别人还有用动态规划做的, 又因为这题刚好是4, 因此还可以用 n&3 != 0 这个写法, 当然不如取余通用.