Medium

题目描述

给你一个整数数组 nums，其中 nums[i] 表示第 i 场游戏中获得的分数。

游戏中有两个玩家。最初，第一个玩家是活跃的，第二个玩家是非活跃的。

对于每场游戏 i，按顺序应用以下规则：

  • 如果 nums[i] 是奇数，活跃和非活跃玩家交换角色。
  • 在每第 6 场游戏中（即游戏索引 5, 11, 17, …），活跃和非活跃玩家交换角色。
  • 活跃玩家进行第 i 场游戏并获得 nums[i] 分数。

返回分数差，定义为第一个玩家的总分数减去第二个玩家的总分数。

示例 1：

输入：nums = [1,2,3]
输出：0
解释：
游戏 0：由于分数是奇数，第二个玩家变为活跃并获得 nums[0] = 1 分。
游戏 1：没有交换发生。第二个玩家获得 nums[1] = 2 分。
游戏 2：由于分数是奇数，第一个玩家变为活跃并获得 nums[2] = 3 分。
分数差是 3 - 3 = 0。

示例 2：

输入：nums = [2,4,2,1,2,1]
输出：4
解释：
游戏 0 到 2：第一个玩家获得 2 + 4 + 2 = 8 分。
游戏 3：由于分数是奇数，第二个玩家现在活跃并获得 nums[3] = 1 分。
游戏 4：第二个玩家获得 nums[4] = 2 分。
游戏 5：由于分数是奇数，玩家交换角色。然后，因为这是第 6 场游戏，玩家再次交换。第二个玩家获得 nums[5] = 1 分。
分数差是 8 - 4 = 4。

示例 3：

输入：nums = [1]
输出：-1
解释：
游戏 0：由于分数是奇数，第二个玩家现在活跃并获得 nums[0] = 1 分。
分数差是 0 - 1 = -1。

约束：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

解题思路

这是一道模拟题，我们需要按照题目给定的规则逐步模拟游戏过程。

思路分析：

核心是要理解两个交换规则的执行顺序和条件：

  1. 奇数交换：如果当前分数是奇数，活跃和非活跃玩家交换角色
  2. 第6场游戏交换：在索引为 5, 11, 17… 的游戏中（即 i % 6 == 5），玩家交换角色

关键点在于理解规则的执行顺序：

  • 先检查奇数交换条件
  • 再检查是否是第6场游戏
  • 最后活跃玩家获得分数

我们可以用一个布尔变量 isFirstPlayerActive 来跟踪当前哪个玩家是活跃的。初始时第一个玩家是活跃的。

算法步骤：

  1. 初始化两个玩家的分数和活跃状态
  2. 遍历每场游戏，按顺序应用规则：
    • 如果分数是奇数，交换玩家角色
    • 如果是第6场游戏（索引 % 6 == 5），交换玩家角色
    • 活跃玩家获得当前分数
  3. 返回第一个玩家分数减去第二个玩家分数

时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int scoreDifference(vector<int>& nums) {
        int firstScore = 0, secondScore = 0;
        bool isFirstPlayerActive = true;
        
        for (int i = 0; i < nums.size(); i++) {
            // Rule 1: If score is odd, swap players
            if (nums[i] % 2 == 1) {
                isFirstPlayerActive = !isFirstPlayerActive;
            }
            
            // Rule 2: Every 6th game (indices 5, 11, 17, ...), swap players
            if (i % 6 == 5) {
                isFirstPlayerActive = !isFirstPlayerActive;
            }
            
            // Rule 3: Active player gains the score
            if (isFirstPlayerActive) {
                firstScore += nums[i];
            } else {
                secondScore += nums[i];
            }
        }
        
        return firstScore - secondScore;
    }
};

class Solution:
    def scoreDifference(self, nums: List[int]) -> int:
        first_score = 0
        second_score = 0
        is_first_player_active = True
        
        for i in range(len(nums)):
            # Rule 1: If score is odd, swap players
            if nums[i] % 2 == 1:
                is_first_player_active = not is_first_player_active
            
            # Rule 2: Every 6th game (indices 5, 11, 17, ...), swap players
            if i % 6 == 5:
                is_first_player_active = not is_first_player_active
            
            # Rule 3: Active player gains the score
            if is_first_player_active:
                first_score += nums[i]
            else:
                second_score += nums[i]
        
        return first_score - second_score

public class Solution {
    public int ScoreDifference(int[] nums) {
        int firstScore = 0, secondScore = 0;
        bool isFirstPlayerActive = true;
        
        for (int i = 0; i < nums.Length; i++) {
            // Rule 1: If score is odd, swap players
            if (nums[i] % 2 == 1) {
                isFirstPlayerActive = !isFirstPlayerActive;
            }
            
            // Rule 2: Every 6th game (indices 5, 11, 17, ...), swap players
            if (i % 6 == 5) {
                isFirstPlayerActive = !isFirstPlayerActive;
            }
            
            // Rule 3: Active player gains the score
            if (isFirstPlayerActive) {
                firstScore += nums[i];
            } else {
                secondScore += nums[i];
            }
        }
        
        return firstScore - secondScore;
    }
}

var scoreDifference = function(nums) {
    let firstPlayerScore = 0;
    let secondPlayerScore = 0;
    let activePlayer = 1; // 1 for first player, 2 for second player
    
    for (let i = 0; i < nums.length; i++) {
        // Check if points are odd
        if (nums[i] % 2 === 1) {
            activePlayer = activePlayer === 1 ? 2 : 1;
        }
        
        // Check if it's every 6th game (indices 5, 11, 17, ...)
        if (i % 6 === 5) {
            activePlayer = activePlayer === 1 ? 2 : 1;
        }
        
        // Active player gains points
        if (activePlayer === 1) {
            firstPlayerScore += nums[i];
        } else {
            secondPlayerScore += nums[i];
        }
    }
    
    return firstPlayerScore - secondPlayerScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，每次操作都是常数时间
空间复杂度O(1)只使用了常数个变量来存储状态