题目地址：

https://www.lintcode.com/problem/valid-tic-tac-toe-state/description

给定一个$3\times 3$的棋盘，两个玩家轮流在棋盘上放字符，先手永远都放$X$，后手永远都放$O$，不能覆盖别人放过字符的地方。如果某方的字符占据了某一行或者某一列或者某一对角线，则这一方获胜。当一方获胜的时候，游戏结束，不允许继续放。给定某个棋盘的状态，问该状态是否合法。

详细思路和证明参考https://blog.csdn.net/qq_46105170/article/details/106010567，下面简要叙述思路。

先遍历棋盘，统计一下几个信息，即先后手是否赢了，先后手字符个数。接下来做判断。首先$X$的个数一定大于等于$O$，并且不能多超过$1$个，否则返回false；如果$X$的个数等于$O$，那么$X$不能赢，否则返回false；如果$X$的个数等于$O$的个数加$1$，则$O$不能赢，否则返回false。其余情况返回true。代码如下：

public class Solution { /** * @param board: the given board * @return: True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game */ public boolean validTicTacToe(String[] board) { // Write your code // 开两个变量存X和O的个数 int xCount = 0, oCount = 0; // 开两个数组存每行每列X或O的个数，X出现计数为1，O出现计数为-1 int[] row = new int[3], col = new int[3]; // 开两个变量记录对角线X或O的个数，X出现计数为1，O出现计数为-1 int diag = 0, antidiag = 0; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length(); j++) { char ch = board[i].charAt(j); if (ch == 'X') { xCount++; row[i]++; col[j]++; if (i == j) { diag++; } if (i + j == 2) { antidiag++; } } else if (ch == 'O') { oCount++; row[i]--; col[j]--; if (i == j) { diag--; } if (i + j == 2) { antidiag--; } } } } // 如果个数不对，返回false if (oCount > xCount || xCount - oCount >= 2) { return false; } // 看一下X和O是否已经赢了 boolean oWin = false, xWin = false; for (int i = 0; i < 3; i++) { if (row[i] == 3 || col[i] == 3) { xWin = true; } if (row[i] == -3 || col[i] == -3) { oWin = true; } } if (diag == 3 || antidiag == 3) { xWin = true; } if (diag == -3 || antidiag == -3) { oWin = true; } // 如果X和O个数相等，那么X不能赢；如果X个数比O多1，则O不能赢 if (xCount == oCount) { return !xWin; } else { return !oWin; } } }

时空复杂度$O(1)$。