题解 | #牛牛的石头游戏#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param piles int整型vector 
     * @return int整型vector
     */
    vector<int> canWin(vector<int>& piles) {
        // write code here
        // 这种谁先手然后一堆规则的游戏一般都是有规律的，拿到题目可以自己随便出一点数字模拟一下
        // 这道题就是每个人每一轮有三种取法选其一，取 1 块，取 2 块，取 3 块
        // 谁把最后一块石头取掉谁就赢了。
        // 问题可以从最简单的情况出发，石头总数是 1，2，3 的时候先手的牛牛稳赢，没什么好说的，
        // 后续的情况全部都可以从前面得到的结果推出。
        // 石头总数是 4 的时候，牛牛先手不管是取多少块，剩下的块数都小于等于 3，后手的人可以一次性取走，
        // 石头总数是 4 这里必输。
        // 石头总数是 5 的时候，牛牛先手取 1 块，问题转化为对手先手且石头总数为 4 的子问题，对手必输。
        // 石头总数是 6 的时候，牛牛先手取 2 块，问题转化为对手先手且石头总数为 4 的子问题，对手必输。
        // 石头总数是 7 的时候，牛牛先手取 3 块，问题转化为对手先手且石头总数为 4 的子问题，对手必输。
        // 石头总数是 8 的时候，牛牛先手不管取多少块，对手都可以将问题转化为自己的对手先手且
        // 石头总数为 4 的子问题，这样牛牛就必输。
        // ......
        // “能否保证自己赢得游戏”的意思其实是牛牛先手取完石头构造一个对手必输的情况就可以了，
        // 而不是说牛牛先手怎么玩都能赢。自己模拟之后会发现只要能构造出
        // “对手先手且石头总数为 4 倍数的子问题” 这样对手就必输，可以保证自己赢得游戏。
        int n = piles.size();
        vector<int> res(n, 1);
        for (int i = 0; i < n; ++i) {
            if (piles[i] % 4 == 0) {
                res[i] = 0;
            }
        }
        return res;
    }
};