1025. 除数博弈
1025. 除数博弈
🟢 🔖 脑筋急转弯
数学
动态规划
博弈
🔗 力扣
LeetCode
题目
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number n
on the chalkboard. On each player's turn, that player makes a move consisting of:
- Choosing any
x
with0 < x < n
andn % x == 0
. - Replacing the number
n
on the chalkboard withn - x
.
Also, if a player cannot make a move, they lose the game.
Return true
if and only if Alice wins the game, assuming both players play optimally.
Example 1:
Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Constraints:
1 <= n <= 1000
题目大意
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字 n
。在每个玩家的回合,玩家需要执行以下操作:
- 选出任一
x
,满足0 < x < n
且n % x == 0
。 - 用
n - x
替换黑板上的数字n
。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 true
。假设两个玩家都以最佳状态参与游戏。
示例 1:
输入: n = 2
输出: true
解释: 爱丽丝选择 1,鲍勃无法进行操作。
示例 2:
输入: n = 3
输出: false
解释: 爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。
提示:
1 <= n <= 1000
解题思路
这道题是一个博弈论问题,需要分析数字 n
的变化过程和两位玩家的策略。爱丽丝和鲍勃都采取最佳策略,这意味着每次都选择对自己最有利的 x
。
取模操作的约束:
- 若
n
为偶数,爱丽丝可以选择x = n / 2
(或者其他任意符合条件的x
),使得n - x
仍然为奇数。 - 若
n
为奇数,所有因数x
也都是奇数,减去任意因数x
后结果变成偶数,交给鲍勃。
- 若
偶数与奇数的规律:
- 偶数:爱丽丝总能确保每次操作后,数字
n
交到鲍勃时是奇数。 - 奇数:鲍勃可以确保每次操作后,数字
n
交到爱丽丝时是偶数。
- 偶数:爱丽丝总能确保每次操作后,数字
游戏的终局:
- 当
n = 1
时,当前玩家无法操作,判定为输。
- 当
因此,游戏的核心在于数字 n
是奇数还是偶数:
- 如果
n
是偶数,爱丽丝总能获胜,因为她可以让数字始终是奇数留给鲍勃,返回true
。 - 如果
n
是奇数,爱丽丝会输,因为最终鲍勃会让n = 1
,返回false
。
复杂度分析
- 时间复杂度:
O(1)
,只需要判断n
是否为偶数。 - 空间复杂度:
O(1)
,不需要额外的空间。
代码
/**
* @param {number} n
* @return {boolean}
*/
var divisorGame = function (n) {
return n % 2 == 0;
};