Easy

题目描述

给你一个正整数数组 nums。

Alice 和 Bob 正在玩一个游戏。在游戏中，Alice 可以从 nums 中选择所有个位数或者所有两位数，剩下的数字归 Bob 所有。如果 Alice 所选数字的和严格大于 Bob 所选数字的和，则 Alice 获胜。

如果 Alice 能赢得这场游戏，返回 true；否则，返回 false。

示例 1：

输入：nums = [1,2,3,4,10]
输出：false
解释：Alice 无论选择个位数还是两位数都无法获胜。

示例 2：

输入：nums = [1,2,3,4,5,14]
输出：true
解释：Alice 可以选择个位数，其和为 15，从而获胜。

示例 3：

输入：nums = [5,5,5,25]
输出：true
解释：Alice 可以选择两位数，其和为 25，从而获胜。

约束：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 99

提示：

  • 如果所有个位数的和与所有两位数的和不相等，Alice 就能获胜。

解题思路

解题思路

这道题的关键在于理解游戏规则：Alice 有两种选择策略，选择所有个位数或选择所有两位数，剩余的数字归 Bob。

核心观察：

  1. 设数组中所有个位数（1-9）的和为 single_sum
  2. 设数组中所有两位数（10-99）的和为 double_sum
  3. 数组总和为 total = single_sum + double_sum

分析 Alice 的两种策略：

  • 策略1：Alice 选择个位数，得到 single_sum，Bob 得到 double_sum
    • Alice 获胜条件：single_sum > double_sum
  • 策略2：Alice 选择两位数，得到 double_sum，Bob 得到 single_sum
    • Alice 获胜条件：double_sum > single_sum

关键洞察： 只要 single_sum ≠ double_sum，Alice 就能获胜！

  • 如果 single_sum > double_sum，Alice 选择策略1
  • 如果 double_sum > single_sum，Alice 选择策略2
  • 只有当 single_sum = double_sum 时，Alice 无法获胜

因此，我们只需要计算个位数和两位数的总和，判断它们是否相等即可。

代码实现

class Solution {
public:
    bool canAliceWin(vector<int>& nums) {
        int singleSum = 0, doubleSum = 0;
        
        for (int num : nums) {
            if (num < 10) {
                singleSum += num;
            } else {
                doubleSum += num;
            }
        }
        
        return singleSum != doubleSum;
    }
};

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        single_sum = sum(num for num in nums if num < 10)
        double_sum = sum(num for num in nums if num >= 10)
        
        return single_sum != double_sum

public class Solution {
    public bool CanAliceWin(int[] nums) {
        int singleSum = 0, doubleSum = 0;
        
        foreach (int num in nums) {
            if (num < 10) {
                singleSum += num;
            } else {
                doubleSum += num;
            }
        }
        
        return singleSum != doubleSum;
    }
}

var canAliceWin = function(nums) {
    let singleSum = 0, doubleSum = 0;
    
    for (let num of nums) {
        if (num < 10) {
            singleSum += num;
        } else {
            doubleSum += num;
        }
    }
    
    return singleSum !== doubleSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历数组一次计算两种数字的和
空间复杂度O(1)，只使用常数额外空间存储两个和值

相关题目