力扣1025. 除數博弈
愛麗絲和鮑勃一起玩遊戲,他們輪流行動。愛麗絲先手開局。
最初,黑板上有一個數字 N
。在每個玩家的回合,玩家需要執行以下操作:
- 選出任一
x
,滿足0 < x < N
且N % x == 0
。 - 用
N - x
替換黑板上的數字N
。
如果玩家無法執行這些操作,就會輸掉遊戲。
只有在愛麗絲在遊戲中取得勝利時才返回 True
,否則返回 False
。假設兩個玩家都以最佳狀態參與遊戲。
示例 1:
輸入:2 輸出:true 解釋:愛麗絲選擇 1,鮑勃無法進行操作。
示例 2:
輸入:3 輸出:false 解釋:愛麗絲選擇 1,鮑勃也選擇 1,然後愛麗絲無法進行操作。
提示:
1 <= N <= 1000
思路:
當N為1時
愛麗絲無法找到一個小於1的正數來整除N,輸,即divisorGame(1)=False,N為2時,愛麗絲取x為1則獲勝,即F(2)=True。
當N>2時
若N從3開始取奇數,滿足N%x == 0的x肯定為奇數,則N-x為偶數,愛麗絲的輸贏肯定和前一個奇數的輸贏情況相同,由於divisorGame(1)=False,所以
divisorGame(>3的奇數)=…=FalsedivisorGame(3)=divisorGame(1)=False
N從4開始取偶數,愛麗絲只要取第一個x為1時,N-1為奇數,此時對方肯定會輸
class Solution: def divisorGame(self, N: int) -> bool: return True if N & 1 == 0 else False