井字游戏

难度: Medium

设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。

以下是井字游戏的规则：

玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。

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

示例 1：

输入： board = ["O X"," XO","X O"]
输出： "X"

示例 2：

输入： board = ["OOX","XXO","OXO"]
输出： "Draw"
解释： 没有玩家获胜且不存在空位

示例 3：

输入： board = ["OOX","XXO","OX "]
输出： "Pending"
解释： 没有玩家获胜且仍存在空位

提示：

1 <= board.length == board[i].length <= 100
输入一定遵循井字棋规则

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def tictactoe(self, board: List[str]) -> str:
        n = len(board)
        def check(c):
            s = c * n
            return any((
                any(row == s for row in board),
                any(col == s for col in map(''.join, zip(*board))),
                all(board[i][i] == c for i in range(n)),
                all(board[i][n - i - 1] == c for i in range(n))
            ))
        if check('X'):
            return 'X'
        if check('O'):
            return 'O'
        if ' ' in ''.join(board):
            return 'Pending'
        return 'Draw'

# 作者：typingMonkey
# 链接：https://leetcode.cn/problems/tic-tac-toe-lcci/solutions/95354/mian-shi-ti-1604-jing-zi-you-xi-by-tuotuoli/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

题解通过定义一个辅助函数 check(c) 来检查字符 c ('X' 或 'O') 是否在任何行、列或对角线上连续出现 N 次。首先，检查每一行和每一列是否存在连续的相同字符。其次，检查两个对角线是否有连续的相同字符。如果字符 'X' 或 'O' 符合上述任一条件，则返回相应的字符表示该玩家获胜。如果棋盘上还有空位（' '），则返回 'Pending' 表示游戏尚未结束。如果棋盘已满且无人获胜，返回 'Draw' 表示平局。

时间复杂度: O(N^2)

空间复杂度: O(1)

class Solution:
    def tictactoe(self, board: List[str]) -> str:
        n = len(board)  # 获取棋盘的大小 N
        def check(c):
            s = c * n  # 创建一个长度为 n 的由字符 c 组成的字符串
            return any((
                any(row == s for row in board),  # 检查每一行是否有连续 n 个 c
                any(col == s for col in map(''.join, zip(*board))),  # 检查每一列是否有连续 n 个 c
                all(board[i][i] == c for i in range(n)),  # 检查主对角线是否全部为 c
                all(board[i][n - i - 1] == c for i in range(n))  # 检查副对角线是否全部为 c
            ))
        if check('X'):
            return 'X'  # 如果 X 获胜，返回 'X'
        if check('O'):
            return 'O'  # 如果 O 获胜，返回 'O'
        if ' ' in ''.join(board):
            return 'Pending'  # 如果有空位，返回 'Pending'
        return 'Draw'  # 否则，返回 'Draw'

Explore

为了确保在较大的棋盘上多轮检查的效率最优化，可以采取以下策略：1. 缓存：在每次玩家下棋后，可以更新一个缓存，记录每一行、每一列、两个对角线上各自字符的计数。这样，每次检查胜利条件时，只需检查这些计数是否达到棋盘大小 N，而不需要重新遍历棋盘。2. 减少重复计算：通过只更新改变的行和列以及可能影响的对角线，而不是每次都检查整个棋盘，从而减少计算量。3. 使用位操作：对于较小的 N（通常 N<=64），可以使用位操作来快速计算行、列或对角线中的连续字符。每一行和列可以表示为一个二进制数，通过位运算来快速判断是否全部位都为1（即全部为 'X' 或 'O'）。

在代码中，可以通过将整个棋盘的所有行连接成一个长字符串，然后检查这个字符串中是否包含空格字符 ' ' 来快速判断棋盘是否还有未填充的空位。具体实现可以使用 Python 的字符串方法 'join' 将所有行连接起来，然后用 'in' 操作符检查 ' ' 是否存在于结果字符串中。例如，使用 `if ' ' in ''.join(board):` 可以高效地判断。

函数 `check(c)` 在检查对角线时，对于主对角线，它检查棋盘上位置 (i, i) （从左上到右下）是否都为字符 c。对于副对角线，它检查位置 (i, n-i-1)（从右上到左下）是否都为字符 c，其中 i 是索引，n 是棋盘的大小。这种方法准确地处理了棋盘的所有边角情况，因为它涵盖了从每个角开始的对角线。只要每个对应的位置符合给定的字符 c，就能正确判断对角线上是否连续。