Easy

题目描述

给你两个下标从 0 开始的整数数组 player1 和 player2，分别表示玩家 1 和玩家 2 在保龄球游戏中击中的瓶数。

保龄球游戏由 n 轮组成，每轮的瓶数恰好为 10。

假设玩家在第 i 轮中击倒了 xi 个瓶子，那么玩家在第 i 轮的得分为：

  • 如果玩家在第 (i-1) 轮或第 (i-2) 轮中击倒了 10 个瓶子，则为 2xi
  • 否则，为 xi

玩家的分数是其 n 轮得分的总和。

返回：

  • 如果玩家 1 的分数大于玩家 2 的分数，则返回 1
  • 如果玩家 2 的分数大于玩家 1 的分数，则返回 2
  • 如果平局，则返回 0

示例 1：

输入：player1 = [5,10,3,2], player2 = [6,5,7,3]
输出：1
解释：
玩家 1 的分数是 5 + 10 + 2*3 + 2*2 = 25
玩家 2 的分数是 6 + 5 + 7 + 3 = 21

示例 2：

输入：player1 = [3,5,7,6], player2 = [8,10,10,2]
输出：2
解释：
玩家 1 的分数是 3 + 5 + 7 + 6 = 21
玩家 2 的分数是 8 + 10 + 2*10 + 2*2 = 42

示例 3：

输入：player1 = [2,3], player2 = [4,1]
输出：0
解释：
玩家 1 的分数是 2 + 3 = 5
玩家 2 的分数是 4 + 1 = 5

示例 4：

输入：player1 = [1,1,1,10,10,10,10], player2 = [10,10,10,10,1,1,1]
输出：2
解释：
玩家 1 的分数是 1 + 1 + 1 + 10 + 2*10 + 2*10 + 2*10 = 73
玩家 2 的分数是 10 + 2*10 + 2*10 + 2*10 + 2*1 + 2*1 + 1 = 75

约束条件：

  • n == player1.length == player2.length
  • 1 <= n <= 1000
  • 0 <= player1[i], player2[i] <= 10

解题思路

这道题是一个典型的模拟题，需要按照题目描述的规则计算两个玩家的总分数，然后比较得出结果。

核心思路：

  1. 分数计算规则：对于第 i 轮，如果玩家在前一轮（第 i-1 轮）或前两轮（第 i-2 轮）中击倒了 10 个瓶子，那么第 i 轮的分数就是 2 * xi，否则就是 xi。

  2. 实现方法：

    • 遍历每一轮，检查当前轮是否需要加倍计分
    • 对于第 i 轮，需要检查 i >= 1 && player[i-1] == 10 或 i >= 2 && player[i-2] == 10
    • 如果满足条件，当前轮得分为 2 * player[i]，否则为 player[i]

  3. 边界处理：

    • 第 0 轮：没有前轮，直接计算 player[0]
    • 第 1 轮：只需检查第 0 轮是否为 10
    • 第 2 轮及以后：需要检查前两轮

  4. 结果比较：计算完两个玩家的总分后，根据大小关系返回对应的结果。

这种直接模拟的方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int isWinner(vector<int>& player1, vector<int>& player2) {
        auto calculateScore = [](const vector<int>& player) {
            int score = 0;
            int n = player.size();
            for (int i = 0; i < n; i++) {
                if ((i >= 1 && player[i-1] == 10) || (i >= 2 && player[i-2] == 10)) {
                    score += 2 * player[i];
                } else {
                    score += player[i];
                }
            }
            return score;
        };
        
        int score1 = calculateScore(player1);
        int score2 = calculateScore(player2);
        
        if (score1 > score2) return 1;
        else if (score2 > score1) return 2;
        else return 0;
    }
};

class Solution:
    def isWinner(self, player1: List[int], player2: List[int]) -> int:
        def calculate_score(player):
            score = 0
            n = len(player)
            for i in range(n):
                if (i >= 1 and player[i-1] == 10) or (i >= 2 and player[i-2] == 10):
                    score += 2 * player[i]
                else:
                    score += player[i]
            return score
        
        score1 = calculate_score(player1)
        score2 = calculate_score(player2)
        
        if score1 > score2:
            return 1
        elif score2 > score1:
            return 2
        else:
            return 0

public class Solution {
    public int IsWinner(int[] player1, int[] player2) {
        int CalculateScore(int[] player) {
            int score = 0;
            int n = player.Length;
            for (int i = 0; i < n; i++) {
                if ((i >= 1 && player[i-1] == 10) || (i >= 2 && player[i-2] == 10)) {
                    score += 2 * player[i];
                } else {
                    score += player[i];
                }
            }
            return score;
        }
        
        int score1 = CalculateScore(player1);
        int score2 = CalculateScore(player2);
        
        if (score1 > score2) return 1;
        else if (score2 > score1) return 2;
        else return 0;
    }
}

/**
 * @param {number[]} player1
 * @param {number[]} player2
 * @return {number}
 */
var isWinner = function(player1, player2) {
    function calculateScore(player) {
        let score = 0;
        for (let i = 0; i < player.length; i++) {
            let multiplier = 1;
            if ((i >= 1 && player[i-1] === 10) || (i >= 2 && player[i-2] === 10)) {
                multiplier = 2;
            }
            score += player[i] * multiplier;
        }
        return score;
    }
    
    const score1 = calculateScore(player1);
    const score2 = calculateScore(player2);
    
    if (score1 > score2) return 1;
    if (score2 > score1) return 2;
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 需要遍历两个数组各一次计算分数
空间复杂度O(1) - 只使用了常数级别的额外空间

相关题目