関小君刷题记

题目大意：

判定井字棋胜负

请在 n × n 的棋盘上，实现一个判定井字棋（Tic-Tac-Toe）胜负的神器，判断每一次玩家落子后，是否有胜出的玩家。

在这个井字棋游戏中，会有 2 名玩家，他们将轮流在棋盘上放置自己的棋子。

在实现这个判定器的过程中，你可以假设以下这些规则一定成立：

    1. 每一步棋都是在棋盘内的，并且只能被放置在一个空的格子里；

    2. 一旦游戏中有一名玩家胜出的话，游戏将不能再继续；

    3. 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子，那么他便获得胜利。

示例:

给定棋盘边长 n = 3, 玩家 1 的棋子符号是 "X"，玩家 2 的棋子符号是 "O"。
 TicTacToe toe = new TicTacToe(3);
 toe.move(0, 0, 1); -> 函数返回 0 (此时，暂时没有玩家赢得这场对决)
 |X| | |
 | | | |    // 玩家 1 在 (0, 0) 落子。
 | | | |
 toe.move(0, 2, 2); -> 函数返回 0 (暂时没有玩家赢得本场比赛)
 |X| |O|
 | | | |    // 玩家 2 在 (0, 2) 落子。
 | | | |
 toe.move(2, 2, 1); -> 函数返回 0 (暂时没有玩家赢得比赛)
 |X| |O|
 | | | |    // 玩家 1 在 (2, 2) 落子。
 | | |X|
 toe.move(1, 1, 2); -> 函数返回 0 (暂没有玩家赢得比赛)
 |X| |O|
 | |O| |    // 玩家 2 在 (1, 1) 落子。
 | | |X|
 toe.move(2, 0, 1); -> 函数返回 0 (暂无玩家赢得比赛)
 |X| |O|
 | |O| |    // 玩家 1 在 (2, 0) 落子。
 |X| |X|
 toe.move(1, 0, 2); -> 函数返回 0 (没有玩家赢得比赛)
 |X| |O|
 |O|O| |    // 玩家 2 在 (1, 0) 落子.
 |X| |X|
 toe.move(2, 1, 1); -> 函数返回 1 (此时，玩家 1 赢得了该场比赛)
 |X| |O|
 |O|O| |    // 玩家 1 在 (2, 1) 落子。
 |X|X|X|

进阶:
您有没有可能将每一步的 move() 操作优化到比 O(n2) 更快吗?

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=348

解题思路分析：

本题难度不大，我们使用4个数组，玩家每走一步我们分别记录每一行，每一列以及两条对角线上X和O的数量，如果某一条线上X或者O的数量等于n，那么该玩家获胜，否则尚未分出胜负。

实现代码：

int[][] countRow;
int[][] countCol;
int[] countDia1;
int[] countDia2;
int length;
/** Initialize your data structure here. */public TicTacToe(int n) {
    length=n;
    countRow=new int[n][3]; // 每一行上X和O的数量
    countCol=new int[n][3]; // 每一列上X和O的数量
    countDia1=new int[3]; // 对角线上X和O的数量
    countDia2=new int[3]; // 反对角线上X和O的数量
}

/** Player {player} makes a move at ({row}, {col}).
    @param row The row of the board.
    @param col The column of the board.
    @param player The player, can be either 1 or 2.
    @return The current winning condition, can be either:
            0: No one wins.
            1: Player 1 wins.
            2: Player 2 wins. */public int move(int row, int col, int player) {
    // 当前行上该玩家棋子数量加一，如果总数量为length，该玩家获胜
    if(++countRow[row][player]==length) return player;
    // 当前列上该玩家棋子数量加一，如果总数量为length，该玩家获胜
    if(++countCol[col][player]==length) return player;
    // 如果是对角线
    if(row==col) {
        // 当前对角线上该玩家棋子数量加1，如果总数量为length，该玩家获胜
        if(++countDia1[player]==length) return player;
    }
    // 如果是反对角线
    if(row+col==length-1) {
        if(++countDia2[player]==length) return player;
    }
    return 0;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 100.00% of Java online submissions for Design Tic-Tac-Toe.

Memory Usage: 41.9 MB, less than 100.00% of Java online submissions for Design Tic-Tac-Toe.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-348-design-tic-tac-toe-解题思路分析/