Easy

题目描述

Alice 和 Bob 正在玩一个游戏，他们轮流从一堆石子中移除石子，Alice 先手。

  • Alice 在她的第一轮中恰好移除 10 个石子。
  • 在每个后续轮次中，每个玩家移除的石子数恰好比前一个对手少 1 个。

无法行动的玩家输掉游戏。

给定一个正整数 n，如果 Alice 赢得游戏则返回 true，否则返回 false。

示例 1：

输入：n = 12
输出：true
解释：
- Alice 在她的第一轮移除 10 个石子，给 Bob 留下 2 个石子。
- Bob 无法移除 9 个石子，所以 Alice 获胜。

示例 2：

输入：n = 1
输出：false
解释：
- Alice 无法移除 10 个石子，所以 Alice 失败。

约束条件：

  • 1 <= n <= 50

解题思路

解题思路

这是一个博弈论问题，我们需要分析游戏规则来确定获胜者。

游戏规则分析：

  1. Alice 第一轮移除 10 个石子
  2. Bob 第二轮移除 9 个石子（比 Alice 少 1）
  3. Alice 第三轮移除 8 个石子（比 Bob 少 1）
  4. 以此类推，每轮移除的石子数依次为：10, 9, 8, 7, 6, 5, 4, 3, 2, 1

解法一：模拟法 直接模拟游戏过程，轮流减去对应数量的石子，直到某一方无法继续。

解法二：数学分析（推荐） 我们可以预先计算出所有可能的游戏回合数：

  • 如果石子总数不足以让 Alice 进行第一步（n < 10），Alice 直接失败
  • 否则，我们可以计算游戏进行的总回合数，判断最后是哪一方无法行动

通过分析可以发现：

  • 移除石子的序列是：10, 9, 8, 7, 6, 5, 4, 3, 2, 1
  • 前 k 项的和为：10 + 9 + … + (11-k) = k*(21-k)/2

我们需要找到最大的 k 使得前 k 项和不超过 n，然后判断 k 的奇偶性。

代码实现

class Solution {
public:
    bool canAliceWin(int n) {
        if (n < 10) return false;
        
        int stones = n;
        int toRemove = 10;
        bool aliceTurn = true;
        
        while (stones >= toRemove) {
            stones -= toRemove;
            aliceTurn = !aliceTurn;
            toRemove--;
        }
        
        return !aliceTurn;
    }
};

class Solution:
    def canAliceWin(self, n: int) -> bool:
        if n < 10:
            return False
        
        stones = n
        to_remove = 10
        alice_turn = True
        
        while stones >= to_remove:
            stones -= to_remove
            alice_turn = not alice_turn
            to_remove -= 1
        
        return not alice_turn

public class Solution {
    public bool CanAliceWin(int n) {
        if (n < 10) return false;
        
        int stones = n;
        int toRemove = 10;
        bool aliceTurn = true;
        
        while (stones >= toRemove) {
            stones -= toRemove;
            aliceTurn = !aliceTurn;
            toRemove--;
        }
        
        return !aliceTurn;
    }
}

var canAliceWin = function(n) {
    if (n < 10) return false;
    
    let stones = n;
    let toRemove = 10;
    let aliceTurn = true;
    
    while (stones >= toRemove) {
        stones -= toRemove;
        aliceTurn = !aliceTurn;
        toRemove--;
    }
    
    return !aliceTurn;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
模拟法O(√n)O(1)
数学法O(1)O(1)

说明： 模拟法的时间复杂度是 O(√n)，因为最多进行约 √(2n) 轮游戏。由于题目约束 n ≤ 50，两种方法的实际性能差异很小。

相关题目