有效的井字游戏

794. 有效的井字游戏

给你一个字符串数组 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' 或 ' '

相似题目

设计井字棋

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool validTicTacToe(vector<string>& board) { } };

javascript 解法, 执行用时: 56 ms, 内存消耗: 40.8 MB, 提交时间: 2023-09-24 23:23:52

/**
 * @param {string[]} board
 * @return {boolean}
 */
var validTicTacToe = function(board) {
    let xCount = 0, oCount = 0;
    for (const row of board) {
        for (const c of row) {
            xCount = (c === 'X') ? (xCount + 1) : xCount;
            oCount = (c === 'O') ? (oCount + 1) : oCount;
        }
    }
    return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
};

const win = (board, p) => {
    for (let i = 0; i < 3; ++i) {
        if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
            (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
            return true;
        }
    }
    return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
            (p == board[0][2] && p == board[1][1] && p == board[2][0]));
}

python3 解法, 执行用时: 32 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-24 23:23:35

class Solution:
    def win(self, board: List[str], p: str) -> bool:
        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or
                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \
                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \
                   board[0][2] == p and board[1][1] == p and board[2][0] == p

    def validTicTacToe(self, board: List[str]) -> bool:
        oCount = sum(row.count('O') for row in board)
        xCount = sum(row.count('X') for row in board)
        return not (oCount != xCount and oCount != xCount - 1 or
                    oCount != xCount and self.win(board, 'O') or
                    oCount != xCount - 1 and self.win(board, 'X'))

java 解法, 执行用时: 0 ms, 内存消耗: 38.4 MB, 提交时间: 2023-09-24 23:23:20

class Solution {
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
    }

    public boolean win(String[] board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0].charAt(i) && p == board[1].charAt(i) && p == board[2].charAt(i)) ||
               (p == board[i].charAt(0) && p == board[i].charAt(1) && p == board[i].charAt(2))) {
                return true;
            }
        }
        return ((p == board[0].charAt(0) && p == board[1].charAt(1) && p == board[2].charAt(2)) ||
                (p == board[0].charAt(2) && p == board[1].charAt(1) && p == board[2].charAt(0)));
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 8.5 MB, 提交时间: 2023-09-24 23:23:10

class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        int xCount = 0, oCount = 0;
        for (string & row : board) {
            for (char c : row) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
    }

    bool win(vector<string>& board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
               (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
                return true;
            }
        }
        return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
                (p == board[0][2] && p == board[1][1] && p == board[2][0]));
    }
};

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-24 23:22:55

// 分类讨论
func win(board []string, p byte) bool {
    for i := 0; i < 3; i++ {
        if board[i][0] == p && board[i][1] == p && board[i][2] == p ||
            board[0][i] == p && board[1][i] == p && board[2][i] == p {
            return true
        }
    }
    return board[0][0] == p && board[1][1] == p && board[2][2] == p ||
        board[0][2] == p && board[1][1] == p && board[2][0] == p
}

func validTicTacToe(board []string) bool {
    oCount, xCount := 0, 0
    for _, row := range board {
        oCount += strings.Count(row, "O")
        xCount += strings.Count(row, "X")
    }
    return !(oCount != xCount && oCount != xCount-1 ||
        oCount != xCount && win(board, 'O') ||
        oCount != xCount-1 && win(board, 'X'))
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-24 23:22:25

func validTicTacToe(board []string) bool {
    isAllSame := func(r,c,dr,dc int) int {
        t := board[r][c]
        if t != ' '{
            for r >= 0 && c >= 0 && r < len(board) && c < len(board[0]) && board[r][c] == t {
                r += dr
                c += dc
            }
            if (dr > 0 && r ==len(board)) || (dc > 0 && c == len(board[0])) {
                if t == 'X' {
                    return 1
                } else{ 
                    return -1
                }
            }
        }
        return 0
    }

    x, o, res := 0, 0, 0
    for i:=0; i<len(board); i++{
        for j:=0; j<len(board[0]);j++ {
            if board[i][j] == 'X'{
                x++
            } else if board[i][j] == 'O'{
                o++
            }
        }
    }
    xw, ow := false, false
    for i := 0; i<len(board);i++ {
        res = isAllSame(i, 0, 0, 1)
        xw = xw || (res == 1)
        ow = ow || (res == -1)
        res = isAllSame(0, i, 1, 0)
        xw = xw || (res == 1)
        ow = ow || (res == -1)
    }
    res = isAllSame(0, 0, 1, 1)
    xw = xw || (res == 1)
    ow = ow || (res == -1)
    res = isAllSame(0, 2, 1, -1)
    xw = xw || (res == 1)
    ow = ow || (res == -1)
    if xw && ow {
        return false
    }
    return (xw && x == o + 1) || (ow && x == o) || (!xw && !ow && (x == o || x == o + 1))
}

javascript 解法, 执行用时: 48 ms, 内存消耗: 40.7 MB, 提交时间: 2023-09-24 23:22:07

/**
 * @param {string[]} board
 * @return {boolean}
 */
/**
 * @param {string[]} board
 * @return {boolean}
 */
var validTicTacToe = function(board) {
    isAllSame = function(r,c,dr,dc){
        const t = board[r].charAt(c)
        if(t != ' '){
            while(r >= 0 && c >= 0 && r < board.length && c < board[0].length && board[r].charAt(c) == t){
                r += dr
                c += dc
            }
            if((dr > 0 && r == board.length) || (dc > 0 && c == board[0].length))
                return t == 'X' ? 1 : -1
        }
        return 0
    }
    let x = 0, o = 0, res
    for(let i=0;i<board.length;i++)
        for(let j=0;j<board[0].length;j++)
            if(board[i].charAt(j) == 'X')
                x++
            else if(board[i].charAt(j) == 'O')
                o++
    let xw = false, ow = false
    for(let i=0;i<board.length;i++){
        res = isAllSame(i, 0, 0, 1)
        xw |= (res == 1)
        ow |= (res == -1)
        res = isAllSame(0, i, 1, 0)
        xw |= (res == 1)
        ow |= (res == -1)
    }
    res = isAllSame(0, 0, 1, 1)
    xw |= (res == 1)
    ow |= (res == -1)
    res = isAllSame(0, 2, 1, -1);
    xw |= (res == 1);
    ow |= (res == -1);
    if(xw && ow)
        return false;
    return (xw && x == o + 1) || (ow && x == o) || (!xw && !ow && (x == o || x == o + 1));
};

python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-09-24 23:21:52

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        x = o = xw = ow = 0
        for row in board:
            s = set(row)
            if len(s) == 1 and (t:=s.pop()) != ' ':
                if t == 'X':
                    xw += 1
                else:
                    ow += 1
            for c in row:
                if c == 'X':
                    x += 1
                elif c == 'O':
                    o += 1
        for c in range(len(board[0])):
            t = board[0][c]
            if t != " ":
                r = 0
                while r < len(board) and board[r][c] == t:
                    r += 1
                if r == len(board):
                    if t == "X":
                        xw += 1
                    else:
                        ow += 1
        mid = board[1][1]
        if mid != " ":
            if board[0][0] == board[1][1] == board[2][2] or board[2][0] == board[1][1] == board[0][2]:
                if mid == "X":
                    xw += 1
                else:
                    ow += 1
        if (x == o or x == o + 1) and not (xw and ow):
            if xw:
                return x == o + 1
            elif ow:
                return x == o
            return True
        return False

java 解法, 执行用时: 0 ms, 内存消耗: 38.8 MB, 提交时间: 2023-09-24 23:21:33

/**
 * X先手，所以个数要么比O多一个，要么一样。 两个人之间只能有一个人赢，
 * 赢的时候，X赢的话必然比O多一个，O赢的话必然和X一样多。
 */
class Solution {
    public boolean validTicTacToe(String[] board) {
        int x = 0, o = 0, res;
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length();j++)
                if(board[i].charAt(j) == 'X')
                    x++;
                else if(board[i].charAt(j) == 'O')
                    o++;
        boolean xw = false, ow = false;
        for(int i=0;i<board.length;i++){
            res = isAllSame(i, 0, 0, 1, board);
            xw |= (res == 1);
            ow |= (res == -1);
            res = isAllSame(0, i, 1, 0, board);
            xw |= (res == 1);
            ow |= (res == -1);
        }
        res = isAllSame(0, 0, 1, 1, board);
        xw |= (res == 1);
        ow |= (res == -1);
        res = isAllSame(0, 2, 1, -1, board);
        xw |= (res == 1);
        ow |= (res == -1);
        if(xw && ow)
            return false;
        return (xw && x == o + 1) || (ow && x == o) || (!xw && !ow && (x == o || x == o + 1));
    }

    private int isAllSame(int r, int c, int dr, int dc, String[] board){
        char t = board[r].charAt(c);
        if(t != ' '){
            while(r >= 0 && c >= 0 && r < board.length && c < board[0].length() && board[r].charAt(c) == t){
                r += dr;
                c += dc;
            }
            if((dr > 0 && r == board.length) || (dc > 0 && c == board[0].length()))
                return t == 'X' ? 1 : -1;
        }
        return 0;
    }
}

上一题

下一题

详情