找出井字棋的获胜者

标签: 数组哈希表矩阵模拟

难度: Easy

A 和 B 在一个 3 x 3 的网格上玩井字棋。

井字棋游戏的规则如下：

玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。
"X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。
只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
如果所有方块都放满棋子（不为空），游戏也会结束。
游戏结束后，棋子无法再进行任何移动。

给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。

如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。

你可以假设 moves 都有效（遵循井字棋规则），网格最初是空的，A 将先行动。

示例 1：

输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出："A"
解释："A" 获胜，他总是先走。
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

示例 2：

输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
输出："B"
解释："B" 获胜。
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

示例 3：

输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
输出："Draw"
解释：由于没有办法再行动，游戏以平局结束。
"XXO"
"OOX"
"XOX"

示例 4：

输入：moves = [[0,0],[1,1]]
输出："Pending"
解释：游戏还没有结束。
"X  "
" O "
"   "

提示：

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
moves 里没有重复的元素。
moves 遵循井字棋的规则。

Submission

运行时间: 15 ms

内存: 16.0 MB

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        Amovesx = []
        Amovesy = []
        Bmovesx = []
        Bmovesy = []
        a = []
        b = []
        c = []
        d = []
        for i in range(len(moves)):
            if i % 2 == 0:
                Amovesx.append((moves[i])[0])
                Amovesy.append((moves[i])[1])
                a.append((moves[i])[0]-(moves[i])[1])
                b.append((moves[i])[0]+(moves[i])[1])
            else:
                Bmovesx.append((moves[i])[0])
                Bmovesy.append((moves[i])[1])
                c.append((moves[i])[0]-(moves[i])[1])
                d.append((moves[i])[0]+(moves[i])[1])
        
        if (Amovesx.count(0) == 3) | (Amovesx.count(1) == 3) | (Amovesx.count(2) == 3) | (Amovesy.count(0) == 3) | (Amovesy.count(1) == 3) | (Amovesy.count(2) == 3):
            return 'A'
        elif (a.count(0) == 3) | (b.count(2) ==3):
            return 'A'
        elif (Bmovesx.count(0) == 3) | (Bmovesx.count(1) == 3) | (Bmovesx.count(2) == 3) | (Bmovesy.count(0) == 3) | (Bmovesy.count(1) == 3) | (Bmovesy.count(2) == 3):
            return 'B'
        elif (c.count(0) == 3) | (d.count(2) == 3):
            return 'B'
        elif (len(Amovesx) + len(Bmovesx)) == 9:
            return 'Draw'
        else:
            return 'Pending'

Explain

该题解的思路是分别记录玩家A和玩家B的棋子位置，然后判断行、列、对角线上是否有连续的三个相同棋子。具体步骤如下： 1. 遍历 moves 数组，根据索引的奇偶性分别记录玩家A和玩家B的棋子位置，并计算对角线上的差值和和值。 2. 判断玩家A的行、列、对角线上是否有连续的三个棋子，如果有则返回 'A'。 3. 判断玩家B的行、列、对角线上是否有连续的三个棋子，如果有则返回 'B'。 4. 如果棋盘已满（即棋子总数为9），则返回 'Draw'。 5. 否则，返回 'Pending'，表示游戏尚未结束。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        Amovesx = []  # 存储玩家A的棋子在行上的位置
        Amovesy = []  # 存储玩家A的棋子在列上的位置
        Bmovesx = []  # 存储玩家B的棋子在行上的位置
        Bmovesy = []  # 存储玩家B的棋子在列上的位置
        a = []  # 存储玩家A的棋子在主对角线上的差值
        b = []  # 存储玩家A的棋子在副对角线上的和值
        c = []  # 存储玩家B的棋子在主对角线上的差值
        d = []  # 存储玩家B的棋子在副对角线上的和值
        
        for i in range(len(moves)):
            if i % 2 == 0:  # 玩家A的回合
                Amovesx.append((moves[i])[0])
                Amovesy.append((moves[i])[1])
                a.append((moves[i])[0]-(moves[i])[1])
                b.append((moves[i])[0]+(moves[i])[1])
            else:  # 玩家B的回合
                Bmovesx.append((moves[i])[0])
                Bmovesy.append((moves[i])[1])
                c.append((moves[i])[0]-(moves[i])[1])
                d.append((moves[i])[0]+(moves[i])[1])
        
        # 判断玩家A是否获胜
        if (Amovesx.count(0) == 3) | (Amovesx.count(1) == 3) | (Amovesx.count(2) == 3) | (Amovesy.count(0) == 3) | (Amovesy.count(1) == 3) | (Amovesy.count(2) == 3):
            return 'A'
        elif (a.count(0) == 3) | (b.count(2) ==3):
            return 'A'
        # 判断玩家B是否获胜
        elif (Bmovesx.count(0) == 3) | (Bmovesx.count(1) == 3) | (Bmovesx.count(2) == 3) | (Bmovesy.count(0) == 3) | (Bmovesy.count(1) == 3) | (Bmovesy.count(2) == 3):
            return 'B'
        elif (c.count(0) == 3) | (d.count(2) == 3):
            return 'B'
        # 判断是否平局
        elif (len(Amovesx) + len(Bmovesx)) == 9:
            return 'Draw'
        # 游戏尚未结束
        else:
            return 'Pending'

Explore

实际上，对角线的检查也是在代码中进行的，但是它是通过变量 `a` 和 `b`（对于玩家A）、`c` 和 `d`（对于玩家B）来实现的。这些变量存储了对角线上棋子的特定属性（差值和和值），这样可以通过检查这些值的计数来判断对角线上是否有三个相同的棋子。因此，虽然看起来只检查了行和列的计数，实际上对角线的检查也被相应地处理了。

`a` 列表存储的是玩家A在主对角线上棋子的行索引与列索引的差值。如果在主对角线上有三个棋子，则这些差值都会是0（例如位置(0,0), (1,1), (2,2)的差值都是0）。`b` 列表存储的是玩家A在副对角线上棋子的行索引与列索引的和值。如果在副对角线上有三个棋子，则这些和值都会是2（例如位置(0,2), (1,1), (2,0)的和值都是2）。检查这些列表的相应值的计数是否为3，可以确定是否在对角线上获胜。

检查 `a.count(0) == 3` 确定所有在主对角线上的棋子的位置，因为主对角线上的位置其行索引与列索引之差总是0。同样，检查 `b.count(2) == 3` 确定所有在副对角线上的棋子的位置，因为副对角线上的位置其行索引与列索引之和总是2。这种方法能准确判断两条对角线上的获胜情况，因为棋盘的大小固定，只有这两条对角线可能满足获胜条件。

使用 `(len(Amovesx) + len(Bmovesx)) == 9` 来判断棋盘是否已满是基于每个玩家的移动次数之和应等于棋盘的格子数（3x3=9）。这是一种有效的方法，因为每次玩家落子都会导致这两个列表的长度增加，直到所有格子都被填满。更直接的方法可能包括直接检查 `moves` 列表的长度是否为9，因为 `moves` 列表的长度直接反映了总的落子次数。