1025. 除數(shù)博弈

題目描述

如果玩家無(wú)法執(zhí)行這些操作，就會(huì)輸?shù)粲螒颉?br> 只有在愛(ài)麗絲在游戲中取得勝利時(shí)才返回 True，否則返回 false。假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲。
愛(ài)麗絲和鮑勃一起玩游戲，他們輪流行動(dòng)。愛(ài)麗絲先手開局。
最初，黑板上有一個(gè)數(shù)字 N 。在每個(gè)玩家的回合，玩家需要執(zhí)行以下操作：

• 選出任一 x，滿足 0 < x < N且 N % x == 0 。
• 用 N - x 替換黑板上的數(shù)字 N 。

如果玩家無(wú)法執(zhí)行這些操作，就會(huì)輸?shù)粲螒颉?br> 只有在愛(ài)麗絲在游戲中取得勝利時(shí)才返回 True，否則返回 false。假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲。

示例1:

輸入：2
輸出：true
解釋：愛(ài)麗絲選擇 1，鮑勃無(wú)法進(jìn)行操作。

示例2:

輸入：3
輸出：false
解釋：愛(ài)麗絲選擇 1，鮑勃也選擇 1，然后愛(ài)麗絲無(wú)法進(jìn)行操作。

解題思路

根據(jù)官方提示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.手撕一個(gè)全世界最優(yōu)秀的玩家出來(lái)，即int theMostBestPlayer(int N)，入?yún)楹诎迳系臄?shù)字，也就是玩家需要把玩的數(shù)字，經(jīng)過(guò)玩家的精心把玩，會(huì)用返回值的方式將數(shù)字再次寫在黑板上。

手撕一個(gè)優(yōu)質(zhì)玩家思路：

1. 當(dāng)拿到一個(gè)偶數(shù)的時(shí)候，努力使其成為一個(gè)奇數(shù)，通過(guò)-1或者減去一個(gè)因數(shù)(官方提示此處略有偏頗)，此處我選擇，能對(duì)半砍，那就對(duì)半砍，比如我們的愛(ài)麗絲拿到數(shù)字10,對(duì)半砍后為5，那我們就把5寫在黑板上, 又比如我們的愛(ài)麗絲拿到了數(shù)字8,對(duì)半砍后還是偶數(shù)，此時(shí)就只能通過(guò)-1操作使其成為奇數(shù)；
2. 當(dāng)拿到一個(gè)奇數(shù)的時(shí)候，努力使其成為一個(gè)偶數(shù)，(官方提示此處很明顯，減去一個(gè)奇數(shù))，此處其實(shí)類似上面一種情況，也只有兩種選擇，要么拿去三分之一(因?yàn)槟萌ヒ粋€(gè)因數(shù)后，余數(shù)依舊為一個(gè)偶數(shù)，那只能是拿去三分之一)，要么-1。
3. 同時(shí)由于有兩位玩家，需要我們?cè)陔p方出手的時(shí)候清楚明白的分清敵我，這里我們使用使用奇數(shù)表示我放愛(ài)麗絲，偶數(shù)表示地方鮑勃，在各方出招之后，將標(biāo)記雙方的player自動(dòng)+1，即將出招回合交給對(duì)方。

根據(jù)示例，我們可知游戲決出勝負(fù)的終止條件為某方拿到的數(shù)字為2或3。

此時(shí)，我們可以分情況處理最終勝負(fù)：

1. 我方愛(ài)麗絲拿到了2，WIN
2. 我方愛(ài)麗絲拿到了3，LOSE
3. 敵方鮑勃拿到了2， LOSE
4. 敵方鮑勃拿到了3， WIN

匯總?cè)缦卤?/strong>：

	Alice	Bob
2	true	false
3	false	true

另外，還有一種特殊情況需要處理，即開局我方愛(ài)麗絲即拿到了數(shù)字1，木得辦法，這種情況必輸無(wú)疑。

LAST BUT NOT LEAST，SHOW THE CODE!!!

代碼

class Solution {
public:
    int theMostBestPlayer(int N)     // 返回值表示黑板上的數(shù)字
    {
        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;              //奇數(shù)表示愛(ài)麗絲
        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;
    }
};

思路通了，敲起代碼來(lái)可謂一氣呵成。一鍵提交，看著雙百的結(jié)果，可謂相當(dāng)?shù)牧钊速p心悅目！

執(zhí)行效率

最后的最后，自我感覺(jué)頗為良好的小小雅克翻開了LeetCode官方答案：

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

不想說(shuō)話