794. 有效的井字游戏状态

Medium

题目描述

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

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

以下是井字游戏的规则：

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

示例 1：

输入：board = ["O  ","   ","   "]
输出：false
解释：第一个玩家总是放置"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'，要么是 ' '

解题思路

这道题需要验证给定的井字游戏状态是否有效，我们需要考虑以下几个方面：

数量关系：由于 X 先手，O 后手，所以 X 的数量应该等于 O 的数量（轮到 O 下棋）或者比 O 多 1（轮到 X 下棋）。
获胜状态检查：检查是否有三子连线（行、列、对角线）。如果有获胜者，需要验证游戏是否在正确的时机结束。
游戏结束逻辑：
- 如果 X 获胜，说明 X 刚下完棋就获胜了，此时 X 的数量应该比 O 多 1
- 如果 O 获胜，说明 O 刚下完棋就获胜了，此时 X 和 O 的数量应该相等
- 不能同时存在两个获胜者

解题步骤：

统计 X 和 O 的数量，验证数量关系
检查所有可能的三子连线情况
根据获胜情况和数量关系判断状态是否有效

这是一道逻辑推理题，需要仔细考虑游戏规则的各种情况。

代码实现

class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        int xCount = 0, oCount = 0;
        
        // 统计X和O的数量
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 'X') xCount++;
                else if (board[i][j] == 'O') oCount++;
            }
        }
        
        // X的数量必须等于O或比O多1
        if (xCount < oCount || xCount > oCount + 1) {
            return false;
        }
        
        // 检查是否有获胜者
        bool xWins = hasWon(board, 'X');
        bool oWins = hasWon(board, 'O');
        
        // 不能同时有两个获胜者
        if (xWins && oWins) {
            return false;
        }
        
        // 如果X获胜，X数量应该比O多1
        if (xWins && xCount != oCount + 1) {
            return false;
        }
        
        // 如果O获胜，X和O数量应该相等
        if (oWins && xCount != oCount) {
            return false;
        }
        
        return true;
    }
    
private:
    bool hasWon(vector<string>& board, char player) {
        // 检查行
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
                return true;
            }
        }
        
        // 检查列
        for (int j = 0; j < 3; j++) {
            if (board[0][j] == player && board[1][j] == player && board[2][j] == player) {
                return true;
            }
        }
        
        // 检查对角线
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player) {
            return true;
        }
        if (board[0][2] == player && board[1][1] == player && board[2][0] == player) {
            return true;
        }
        
        return false;
    }
};

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        x_count = 0
        o_count = 0
        
        # 统计X和O的数量
        for row in board:
            x_count += row.count('X')
            o_count += row.count('O')
        
        # X的数量必须等于O或比O多1
        if x_count < o_count or x_count > o_count + 1:
            return False
        
        # 检查是否有获胜者
        x_wins = self.has_won(board, 'X')
        o_wins = self.has_won(board, 'O')
        
        # 不能同时有两个获胜者
        if x_wins and o_wins:
            return False
        
        # 如果X获胜，X数量应该比O多1
        if x_wins and x_count != o_count + 1:
            return False
        
        # 如果O获胜，X和O数量应该相等
        if o_wins and x_count != o_count:
            return False
        
        return True
    
    def has_won(self, board, player):
        # 检查行
        for row in board:
            if all(cell == player for cell in row):
                return True
        
        # 检查列
        for j in range(3):
            if all(board[i][j] == player for i in range(3)):
                return True
        
        # 检查对角线
        if all(board[i][i] == player for i in range(3)):
            return True
        if all(board[i][2-i] == player for i in range(3)):
            return True
        
        return False

public class Solution {
    public bool ValidTicTacToe(string[] board) {
        int xCount = 0, oCount = 0;
        
        // 统计X和O的数量
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 'X') xCount++;
                else if (board[i][j] == 'O') oCount++;
            }
        }
        
        // X的数量必须等于O或比O多1
        if (xCount < oCount || xCount > oCount + 1) {
            return false;
        }
        
        // 检查是否有获胜者
        bool xWins = HasWon(board, 'X');
        bool oWins = HasWon(board, 'O');
        
        // 不能同时有两个获胜者
        if (xWins && oWins) {
            return false;
        }
        
        // 如果X获胜，X数量应该比O多1
        if (xWins && xCount != oCount + 1) {
            return false;
        }
        
        // 如果O获胜，X和O数量应该相等
        if (oWins && xCount != oCount) {
            return false;
        }
        
        return true;
    }
    
    private bool HasWon(string[] board, char player) {
        // 检查行
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
                return true;
            }
        }
        
        // 检查列
        for (int j = 0; j < 3; j++) {
            if (board[0][j] == player && board[1][j] == player && board[2][j] == player) {
                return true;
            }
        }
        
        // 检查对角线
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player) {
            return true;
        }
        if (board[0][2] == player && board[1][1] == player && board[2][0] == player) {
            return true;
        }
        
        return false;
    }
}

var validTicTacToe = function(board) {
    let xCount = 0, oCount = 0;
    
    // Count X's and O's
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i][j] === 'X') xCount++;
            else if (board[i][j] === 'O') oCount++;
        }
    }
    
    // X should have same count or one more than O
    if (oCount > xCount || xCount > oCount + 1) return false;
    
    // Check if someone won
    const hasWon = (player) => {
        // Check rows and columns
        for (let i = 0; i < 3; i++) {
            if ((board[i][0] === player && board[i][1] === player && board[i][2] === player) ||
                (board[0][i] === player && board[1][i] === player && board[2][i] === player)) {
                return true;
            }
        }
        // Check diagonals
        if ((board[0][0] === player && board[1][1] === player && board[2][2] === player) ||
            (board[0][2] === player && board[1][1] === player && board[2][0] === player)) {
            return true;
        }
        return false;
    };
    
    const xWon = hasWon('X');
    const oWon = hasWon('O');
    
    // Both can't win
    if (xWon && oWon) return false;
    
    // If X won, X should have exactly one more than O
    if (xWon && xCount !== oCount + 1) return false;
    
    // If O won, counts should be equal
    if (oWon && xCount !== oCount) return false;
    
    return true;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	值
时间复杂度	O(1)
空间复杂度	O(1)

由于棋盘大小固定为 3×3，所有操作都是常数时间，因此时间和空间复杂度都是 O(1)。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目