有效的井字游戏

难度: Medium

给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 board 所显示的状态时，才返回 true 。

井字游戏的棋盘是一个 3 x 3 数组，由字符 ' '，'X' 和 'O' 组成。字符 ' ' 代表一个空位。

以下是井字游戏的规则：

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

示例 1：

输入：board = ["O  ","   ","   "]
输出：false
解释：玩家 1 总是放字符 "X" 。

示例 2：

输入：board = ["XOX"," X ","   "]
输出：false
解释：玩家应该轮流放字符。

示例 3:

输入：board = ["XOX","O O","XOX"]
输出：true

提示：

board.length == 3
board[i].length == 3
board[i][j] 为 'X'、'O' 或 ' '

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        o_num = 0
        x_num = 0
        for i in range(3):
            for j in range(3):
                if board[i][j] == 'O':
                    o_num += 1
                if board[i][j] == 'X':
                    x_num += 1
                pass
        x_win_num = 0
        o_win_num = 0
        for i in range(3):
            if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
                if board[i][0] == 'X':
                    x_win_num += 1
                elif board[i][0] == 'O':
                    o_win_num += 1
            elif board[0][i] == board[1][i] and board[1][i] == board[2][i]:
                if board[0][i] == 'X':
                    x_win_num += 1
                elif board[0][i] == 'O':
                    o_win_num += 1
                pass
        
        
        print(x_win_num,o_win_num)
        if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == 'X':
                x_win_num += 1
            elif board[0][0] == 'O':
                o_win_num += 1
        
        if board[0][2] == board[1][1] and board[1][1] == board[2][0]:
            if board[2][0] == 'X':
                x_win_num += 1
            elif board[2][0] == 'O':
                o_win_num += 1
           
            

        
        if o_num > x_num or x_num > o_num + 1:
            return False
        elif x_win_num > 0 and o_win_num > 0:
            return False
        elif x_win_num > 0 and x_num < o_num + 1:
            return False
        elif o_win_num > 0 and x_num > o_num:
            return False
        else:
            return True

Explain

这个题解的思路是先统计棋盘上 'X' 和 'O' 的个数，然后再统计 'X' 和 'O' 各自形成连线获胜的次数。最后根据题目规则判断棋盘状态是否合法。具体判断标准为：1. 'O' 的个数不能大于 'X' 的个数，且 'X' 的个数最多比 'O' 多1个；2. 'X' 和 'O' 不能同时形成连线获胜；3. 如果 'X' 形成连线获胜，则此时 'X' 的个数必须恰好比 'O' 多1个；4. 如果 'O' 形成连线获胜，则此时 'X' 和 'O' 的个数必须相等。只有同时满足以上条件，才是一个合法的棋盘状态。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        # 统计棋盘上 'O' 的个数
        o_num = 0
        # 统计棋盘上 'X' 的个数 
        x_num = 0
        # 双重循环遍历棋盘
        for i in range(3):
            for j in range(3):
                if board[i][j] == 'O':
                    o_num += 1
                if board[i][j] == 'X':
                    x_num += 1
                
        # 统计 'X' 形成连线获胜的次数
        x_win_num = 0
        # 统计 'O' 形成连线获胜的次数
        o_win_num = 0
        # 检查每一行
        for i in range(3):
            if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
                if board[i][0] == 'X':
                    x_win_num += 1
                elif board[i][0] == 'O':
                    o_win_num += 1
            # 检查每一列
            elif board[0][i] == board[1][i] and board[1][i] == board[2][i]:
                if board[0][i] == 'X':
                    x_win_num += 1
                elif board[0][i] == 'O':
                    o_win_num += 1
                
        # 检查正对角线
        if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == 'X':
                x_win_num += 1
            elif board[0][0] == 'O':
                o_win_num += 1
        
        # 检查反对角线
        if board[0][2] == board[1][1] and board[1][1] == board[2][0]:
            if board[2][0] == 'X':
                x_win_num += 1
            elif board[2][0] == 'O':
                o_win_num += 1
        
        # 判断棋盘状态是否合法
        if o_num > x_num or x_num > o_num + 1:
            return False
        elif x_win_num > 0 and o_win_num > 0:
            return False
        elif x_win_num > 0 and x_num <= o_num:
            return False
        elif o_win_num > 0 and x_num > o_num:
            return False
        else:
            return True

Explore

在代码中，每行和每列的胜利情况是分开检查的，而且对于每行每列的检查都是独立的。这意味着，即使某一行或某一列出现胜利情况，它们各自的胜利都会被独立计算，不会互相影响。但实际上，代码中并没有机制来防止对角线胜利和行或列胜利重复计数，所以如果一个行或列同时也是对角线的一部分并且形成了胜利，那么胜利次数会被重复计算。因此，代码需要进一步优化以防止这种重复计数。

在代码中使用elif而不是if来检查列的胜利情况是一个错误，因为这样排除了某一行和某一列可能同时获胜的情况。如果某一行和某一列在同一轮循环中都符合获胜条件，使用elif就会导致该列的胜利情况被忽略，只计算行的胜利。这是一个潜在的bug，应该将elif改为if以确保行和列的胜利都能被正确统计。

如果'X'或'O'在对角线上获胜，同时在行或列中也形成了连线，这将导致胜利次数被重复计算。例如，如果一个'X'在第一行和主对角线上同时形成了连线，这将使'X'的胜利次数增加两次。这种情况在代码中没有被特别处理，因此可能导致对游戏状态的错误判断。

这个规则反映了井字游戏的基本规则：玩家轮流放置'X'和'O'。游戏开始时，'X'先行，因此每当'X'获胜时，由于'X'总是先行，'X'的数量必须比'O'多1。相对地，如果'O'获胜，因为'O'是第二个行动，此时'X'和'O'的数量必须相等，说明'O'在其最后一次行动中获胜，而在此之前'X'和'O'的数量是平衡的。这些规则确保了游戏的正常轮换和公平性。