跳至主要內容

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 < n 且 n % 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;
};