手撕一个全世界最优(luo)质(zhi)的博弈专家

1025. 除数博弈

题目描述

如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 x，满足 0 < x < N且 N % x == 0 。
• 用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例1:

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例2:

输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

解题思路

根据官方提示If the current number is even, we can always subtract a 1 to make it odd. If the current number is odd, we must subtract an odd number to make it even.手撕一个全世界最优秀的玩家出来，即int theMostBestPlayer(int N)，入参为黑板上的数字，也就是玩家需要把玩的数字，经过玩家的精心把玩，会用返回值的方式将数字再次写在黑板上。

手撕一个优质玩家思路：

1. 当拿到一个偶数的时候，努力使其成为一个奇数，通过-1或者减去一个因数(官方提示此处略有偏颇)，此处我选择，能对半砍，那就对半砍，比如我们的爱丽丝拿到数字10,对半砍后为5，那我们就把5写在黑板上, 又比如我们的爱丽丝拿到了数字8,对半砍后还是偶数，此时就只能通过-1操作使其成为奇数；
2. 当拿到一个奇数的时候，努力使其成为一个偶数，(官方提示此处很明显，减去一个奇数)，此处其实类似上面一种情况，也只有两种选择，要么拿去三分之一(因为拿去一个因数后，余数依旧为一个偶数，那只能是拿去三分之一)，要么-1。
3. 同时由于有两位玩家，需要我们在双方出手的时候清楚明白的分清敌我，这里我们使用使用奇数表示我放爱丽丝，偶数表示地方鲍勃，在各方出招之后，将标记双方的player自动+1，即将出招回合交给对方。

根据示例，我们可知游戏决出胜负的终止条件为某方拿到的数字为2或3。

此时，我们可以分情况处理最终胜负：

1. 我方爱丽丝拿到了2，WIN
2. 我方爱丽丝拿到了3，LOSE
3. 敌方鲍勃拿到了2， LOSE
4. 敌方鲍勃拿到了3， WIN

汇总如下表：

	Alice	Bob
2	true	false
3	false	true

另外，还有一种特殊情况需要处理，即开局我方爱丽丝即拿到了数字1，木得办法，这种情况必输无疑。

LAST BUT NOT LEAST，SHOW THE CODE!!!

代码

class Solution {
public:
    int theMostBestPlayer(int N)     // 返回值表示黑板上的数字
    {
        if(N%2==0)
        {
            if((N/2)%2 == 1)
                return N/2;
        }
        else
        {
            if(N%3==0)
                return N/3*2;
        }
        return N-1;
    }

    bool divisorGame(int N) {
        if(N == 1)
            return false;
        int player = 1;              //奇数表示爱丽丝
        while(N != 2 && N != 3)
        {
            N = theMostBestPlayer(N);
            player++;
        }
        if(player%2==0 && N == 2)
            return false;
        if(player%2==0 && N == 3)
            return true;
        if(player%2==1 && N == 2)
            return true;
        if(player%2==1 && N == 3)
            return false;
        return false;
    }
};

思路通了，敲起代码来可谓一气呵成。一键提交，看着双百的结果，可谓相当的令人赏心悦目！

执行效率

最后的最后，自我感觉颇为良好的小小雅克翻开了LeetCode官方答案：

bool divisorGame(int N) {
  return N % 2 == 0;
}

不想说话