348. Design Tic-Tac-Toe

LeetCode Link

size 为 n 的棋牌，player1 和 player2 轮流向空处置子，当 row, column or diagonal 有 n 个相同的子，游戏结束，返回胜利的player，否则返回 0.

initial implementation

class TicTacToe {
    int[][] board;
    int size;
    
    public TicTacToe(int n) {
        size = n;
        board = new int[n][n];
    }
    
    // if the player wins, return the player; otherwise, return 0
    public int move(int row, int col, int player) {
        board[row][col] = player;
        
        // row
        int playerCnt = 0;
        for (int i = 0; i < size; i++) {
            if (board[row][i] == player) {
                playerCnt++;
            } else {
                break;
            }
        }
        
        if (playerCnt == size) {
            return player;
        }
        
        // col
        playerCnt = 0;
        for (int i = 0; i < size; i++) {
            if (board[i][col] == player) {
                playerCnt++;
            } else {
                break;
            }
        }
        
        if (playerCnt == size) {
            return player;
        }
        
        // left top to right bottom diagonal
        playerCnt = 0;
        if (row == col) {
            for (int i = 0; i < size; i++) {
                if (board[i][i] == player) {
                    playerCnt++;
                } else {
                    break;
                }
            }
        }
        
        if (playerCnt == size) {
            return player;
        }
        
        // left bottom to right top diagonal
        playerCnt = 0;
        if (row + col == size - 1) {
            for (int i = 0; i < size; i++) {
                if (board[i][size - 1 - i] == player) {
                    playerCnt++;
                } else {
                    break;
                }
            }
        }
        
        if (playerCnt == size) {
            return player;
        }
        
        return 0;
    }
}

这个题目本身假设每一次 move 都是有效的，也就是说，并不需要记录 board 具体每个 cell 的值。因此可以优化成下面的代码：

class TicTacToe {
    int size;
    int[][] rowCount;
    int[][] colCount;
    int[] topToBottom;
    int[] bottomToTop;
    
    public TicTacToe(int n) {
        size = n;
        // rowCount[playerIndex][row]: token count of player (playerIndex + 1) at row 'row' of the board
        rowCount = new int[2][n];
        
        // colCount[playerIndex][col]: token count of player (playerIndex + 1) at column 'col' of the board
        colCount = new int[2][n];
        
        // topToBottom[playerIndex]: token count of player (playerIndex + 1) on the diagonal top to bottom
        topToBottom = new int[2];
        
        // bottomToTop[playerIndex]: token count of player (playerIndex + 1) on the diagonal bottom to top
        bottomToTop = new int[2];
    }
    
    // if the player wins, return the player; otherwise, return 0
    public int move(int row, int col, int player) {
        int playerIndex = player - 1;
        
        rowCount[playerIndex][row] += 1;
        colCount[playerIndex][col] += 1;
        if (row == col) {
            topToBottom[playerIndex] += 1;
        }
        if (row + col == size - 1) {
            bottomToTop[playerIndex] += 1;
        }
        
        if (rowCount[playerIndex][row] == size || colCount[playerIndex][col] == size 
                || topToBottom[playerIndex] == size || bottomToTop[playerIndex] == size) {
            return player;
        }
        
        return 0;
    }
}

Runtime: O(n) -> O(1)
Space: O(n ^ 2) -> O(n)

上面题解的二维数组还可以进一步优化为一维数组。

int step = (player == 1) ? 1: -1;

rows[row] += step;
cols[col] += step;
diagonal += step if row == col
antiDiagonal += step if row + col == size - 1

return player if (any == size || any == -size)