LeetCode 1275. 找出井字棋的获胜者

题目描述

给你一个数组 moves，其中 moves[i] = [row_i, col_i] 表示第 i 步在 3 x 3 的井字棋棋盘上的落子位置。棋盘从空棋盘开始。

两名玩家轮流下棋，玩家 A 执 “X” 子，玩家 B 执 “O” 子。玩家 A 总是先手。

如果游戏存在获胜者（即同一玩家在任意行、列或对角线上拥有三颗连续棋子），则返回该获胜者（“A” 或 “B”）。
如果游戏以平局结束，则返回 “Draw”。
如果游戏仍然在进行中（即棋盘上还有空位，且无人获胜），则返回 “Pending”。

题目保证 moves 是有效的（即棋盘上不会在已落子的位置重复落子）。

解题过程

我们可以模拟整个对弈过程，在每一步之后检查是否有玩家获胜。核心是高效地判断获胜条件。

步骤 1: 确定数据结构与获胜条件

棋盘是 3x3，我们可以用两个数组分别记录玩家 A 和玩家 B 在每一行、每一列以及两条主对角线上拥有的棋子数量。

1. 行与列： 棋盘有 3 行 3 列。如果某个玩家在任意一行（或列）的棋子数达到 3，则该玩家获胜。
2. 对角线：
   • 主对角线： 行索引 i 等于列索引 j 的位置（即 (0,0), (1,1), (2,2)）。
   • 反对角线： 行索引 i 与列索引 j 满足 i + j == 2 的位置（即 (0,2), (1,1), (2,0)）。

我们可以为每位玩家定义四个长度为 3 的数组：

• rows[3]: 记录在每一行落子的个数。
• cols[3]: 记录在每一列落子的个数。
• diag1: 记录在主对角线（i == j）上落子的个数。
• diag2: 记录在反对角线（i + j == 2）上落子的个数。

步骤 2: 模拟对弈过程

1. 初始化：

   • 为玩家 A 和玩家 B 各创建一组计数数组（rows, cols）和计数器（diag1, diag2）。
   • 或者，更简洁的方法是：用 +1 代表玩家 A 的落子，-1 代表玩家 B 的落子。然后只维护一个公共的计数集合。当某行/列/对角线的绝对值达到 3 时，即可判断获胜者。但为了清晰，我们按两位玩家分开讲解。

2. 遍历每一步棋 moves[i] = [r, c]：

   • 确定当前棋手：索引 i 是偶数（0, 2, 4...）时，是玩家 A 下棋；是奇数（1, 3, 5...）时，是玩家 B 下棋。
   • 根据棋手，更新其对应的计数数组：
     • rows[r] += 1
     • cols[c] += 1
     • 如果 r == c，则 diag1 += 1
     • 如果 r + c == 2，则 diag2 += 1

3. 检查获胜条件：

   • 在更新计数后，立即检查当前棋手的计数是否满足以下任意条件：
     • rows[r] == 3 或
     • cols[c] == 3 或
     • diag1 == 3 或
     • diag2 == 3
   • 如果满足，游戏结束，立即返回当前棋手（“A” 或 “B”）。

步骤 3: 处理平局或进行中

遍历完所有步骤后：

1. 如果过程中已返回获胜者，则问题已解决。
2. 如果没有获胜者，则检查棋盘是否已满：
   • 井字棋棋盘共有 9 个格子。moves 数组的长度 len(moves) 表示已下的步数。
   • 如果 len(moves) == 9，意味着棋盘已满且无人获胜，结果为 “Draw”。
   • 如果 len(moves) < 9，意味着棋盘还有空位且无人获胜，结果为 “Pending”。

举例说明

以 moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 为例：

1. 步 0 ([0,0]): 玩家 A 在 (0,0) 下子。
   • A: rows[0]=1, cols[0]=1, diag1=1。不满足获胜条件。
2. 步 1 ([2,0]): 玩家 B 在 (2,0) 下子。
   • B: rows[2]=1, cols[0]=1。不满足。
3. 步 2 ([1,1]): 玩家 A 在 (1,1) 下子。
   • A: rows[1]=1, cols[1]=1, diag1=2, diag2=1。不满足。
4. 步 3 ([2,1]): 玩家 B 在 (2,1) 下子。
   • B: rows[2]=2, cols[1]=1。不满足。
5. 步 4 ([2,2]): 玩家 A 在 (2,2) 下子。
   • A: rows[2]=1, cols[2]=1, diag1 变为 3（因为 (0,0), (1,1), (2,2) 都是 A 下的）。
   • 检查发现 diag1 == 3，满足获胜条件。游戏结束，返回 “A”。

代码思路（非具体实现，供理解逻辑）

def tictactoe(moves):
    # 初始化计数：用+1代表A，-1代表B
    rows, cols = [0, 0, 0], [0, 0, 0]
    diag1 = diag2 = 0
    player = 1  # 1代表A，-1代表B

    for step, (r, c) in enumerate(moves):
        # 1. 更新计数
        rows[r] += player
        cols[c] += player
        if r == c:
            diag1 += player
        if r + c == 2:
            diag2 += player

        # 2. 检查当前玩家是否获胜
        if (abs(rows[r]) == 3 or abs(cols[c]) == 3 or
            abs(diag1) == 3 or abs(diag2) == 3):
            return "A" if player == 1 else "B"

        # 3. 切换玩家
        player = -player

    # 3. 遍历结束，未分胜负
    if len(moves) == 9:
        return "Draw"
    else:
        return "Pending"

总结

这道题的关键在于，将“检查是否有连续三个相同棋子”这个二维平面上的判断，转化为对行、列、对角线上棋子数量的累加判断。通过为每位玩家维护简单的计数数组，我们可以在每一步落子后，以 O(1) 的时间复杂度检查当前玩家是否刚刚完成了制胜一手。整个算法只需顺序遍历一次 moves 数组，时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。