292. Nim 游戏

// (n - 1) && (n -2) && (n -3)：这些是 n - 1，n - 2，n - 3 只剩这些石头，出手会不会赢
// &&：我当然不会让他赢啦，只要有一个能让他输，我就拿多少石头
// !：((n - 1) && (n -2) && (n -3)) 用来判断他是否会赢，如果他赢不了，那就是我赢
// 这一整条都是用来计算我出手会不会赢
n = !((n - 1) && (n -2) && (n -3))

/**
 * 超出时间限制问题，已通过 50 个测试用例
 * @param n 石头数量
 * @return 我是否能够获胜
 */
public boolean canWinNim(int n) {
    // 我先出手，所以我直接赢了
    if (n == 1 || n == 2 || n == 3) {
        return true;
    }
    // 用来保存，前 3 个石头出手能获胜的概率
    boolean[] result = new boolean[3];
    // 只剩 1 - 3 个石头时，谁出手谁获胜
    result[0] = result[1] = result[2] = true;
    int index = 3;
    while(index < n){
        // (n - 1) && (n -2) && (n -3)：这些是 n - 1，n - 2，n - 3 只剩这些石头，出手会不会赢
        // &&：我当然不会让他赢啦，只要有一个能让他输，我就拿多少石头
        // !：((n - 1) && (n -2) && (n -3)) 用来判断他是否会赢，如果他赢不了，那就是我赢
        // 这一整条都是用来计算我出手会不会赢
        boolean flag = !(result[0] && result[1] && result[2]);
        move(result, flag);
        index++;
    }
    // 最后一个就是答案了
    return result[2];
}

/**
 * 将答案往前移动
 */
public void move(boolean[] flags, boolean flag){
    flags[0] = flags[1];
    flags[1] = flags[2];
    flags[2] = flag;
}

/**
 * 优化版本，使用位运算
 * 超出时间限制问题，已通过 52 个测试用例
 * @param n 石头数量
 * @return 我是否能够获胜
 */
public boolean canWinNim(int n) {
    // 我先出手，所以我直接赢了
    if (n == 1 || n == 2 || n == 3) {
        return true;
    }
    // 代表到谁拿石头的输赢情况 0：代表输，1：代表赢
    // 二进制 0000 0111
    byte result = 0b111;
    // 赢的情况
    byte sureWin = 0b111;
    int index = 3;
    while(index < n){
        // & 运算：只有两位都是 1，结果才是 1
        // result & sureWin：用来判断他是否会赢，要是前面都是下一个人赢，那么我怎么拿都是输
        // (result & sureWin) == sureWin：也就是说 右边三位都是 1
        boolean myWin = !((result & sureWin) == sureWin);
        // 将所有位 左移动一位
        // 例如：result = 0000 0111，左移动一位，result = 0000 1110
        result <<= 1;
        // 如果赢了，就需要给最右边位改为 1
        if (myWin){
            result |= 1;
        }
        index++;
    }
    // 最后位是 1，代表我赢，是 0，代表我输
    return (result & 1) == 1;
}

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