跳至主要內容

1025. 除数博弈


1025. 除数博弈

🟢   🔖  脑筋急转弯 数学 动态规划 博弈  🔗 力扣open in new window LeetCodeopen in new window

题目

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 with 0 < x < n and n % x == 0.
  • Replacing the number n on the chalkboard with n - 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 < nn % x == 0
  • n - x 替换黑板上的数字 n

如果玩家无法执行这些操作,就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1:

输入: n = 2

输出: true

解释: 爱丽丝选择 1,鲍勃无法进行操作。

示例 2:

输入: n = 3

输出: false

解释: 爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

提示:

  • 1 <= n <= 1000

解题思路

这道题是一个博弈论问题,需要分析数字 n 的变化过程和两位玩家的策略。爱丽丝和鲍勃都采取最佳策略,这意味着每次都选择对自己最有利的 x

  1. 取模操作的约束

    • n 为偶数,爱丽丝可以选择 x = n / 2(或者其他任意符合条件的 x),使得 n - x 仍然为奇数。
    • n 为奇数,所有因数 x 也都是奇数,减去任意因数 x 后结果变成偶数,交给鲍勃。
  2. 偶数与奇数的规律

    • 偶数:爱丽丝总能确保每次操作后,数字 n 交到鲍勃时是奇数。
    • 奇数:鲍勃可以确保每次操作后,数字 n 交到爱丽丝时是偶数。
  3. 游戏的终局

    • 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;
};