leetCode-292:Nim Game

问题描述

有这么一个游戏：两人对玩，有这么一堆石头，每次都从石头中取出 1 或 2 或 3 个石头，最后一个石头是谁拿走则谁胜出。现在给定一个数字表示有 n 个石头，要求游戏中先手是否能获胜。题目链接：点我

样例输入输出

输入：4

输出：false

解释：假设先手拿了 1 个石头，则后手拿走剩下 3 个石头（包含最后一块石头），先手输

假设先手拿了 2 个石头，则后手拿走剩下 2 个石头（包含最后一块石头），先手输

假设先手拿了 3 个石头，则后手拿走剩下 1 个石头（包含最后一块石头），先手输

输入：2

输出：true

解释：先手一次行拿走 2 个石头（包含最后一个石头），先手赢

问题解法

石头在 [1, 3] 范围内，先手都赢，因为可以直接拿走所有的石头（包括最后一个石头），石头数量是 4 的时候，先手都输，因为无论先手拿 [1, 3] 中的任何一个石头，后手都可以直接拿走剩下的全部石头（包括最后一个石头）。如果石头数量是 5，则先手可以拿走 1 个石头，剩下的 4 个石头无论后手如何取都会失败（前面论证过 4 个石头的情况下先拿的人会失败），即先手胜。如果石头数量是 6，则先手可以拿走 2 个石头，剩下 4 个石头无论后手如何选择最终都会输掉游戏，即先手胜利。如果石头数量是 7，则先手可以拿走 3 个石头，剩下 4 个石头无论后手如何选择最终都会输掉游戏，即先手胜利。如果石头数量是 8，则先手无论取走多少个石头，后手都能将剩下的石头数变成 4（如果先手取 1，则后手取 3；如果先手取 2，则后手取 2；如果先手取 3，则后手取 1），此时先手无论如何取石头最终都会输掉游戏（参考前面对石头数量为 4 的分析）。如果石头数量是 9，则先手可以拿走 1 个石头，剩下 8 个石头无论后手如何取都会失败（最终表现为先手胜利），依次类推，可以得知，如果石头数量是 4 的倍数，则先手失败，否则先手胜利。因此，次题解转换为对 n % 4 的判断。代码如下

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