0292. Nim Game #

题目 #

• 两人玩 Nim 游戏

  • 桌子上有一堆石头。

  • 每一回合，轮到的人拿掉 1 - 3 块石头。

  • 拿掉最后一块石头的人就是获胜者。

• 假设两人所走每一步都是最优解。

• 编写函数，判断先手能否在给定石头数量为 n 的情况下赢得游戏。

思路 #

博弈 #

• 若 n 不是 4 的幂，则在每回合先手总可以令后手面对总数为 4的若干次幂 的石头，直至令后手面对 4块石头。此时先手必胜。
• 同理，若 n 是 4 的幂，则先手必败。

代码 #

博弈 #

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