LeetCode 面试题 16.04. 井字游戏
题目描述
题意分析
判断当前 $n \times n$ 棋盘是
X获胜、O获胜、仍可继续的Pending，还是无人获胜且已经填满的Draw。获胜要求某一整行、整列、主对角线或副对角线全是同一个非空字符。题目保证输入符合游戏规则，因此不需要另行判断双方落子数或胜者是否合法。先检查有没有获胜者；只有确定无人获胜后，空格是否存在才用于区分
Pending和Draw。将
X编码为1、O编码为-1，就能把整条线是否属于同一玩家转成整数和判断，在一次扫描中同时维护全部候选直线。
解法：行列与对角线计数
核心思路
[!blue]
rows[i]、cols[j]分别保存对应行列中已经扫描部分的编码和，dg保存主对角线的和，udg保存副对角线的和。遇到非空格时把当前编码加入所在行列；只有i == j才属于主对角线，只有i + j == n - 1才属于副对角线。一条线有
n个位置，每个位置最多贡献1，最少贡献-1。只有全部n个位置都为X时总和才可能达到n，全部为O时才可能达到-n；存在空格或混入另一方，绝对值都会小于n。因此判断绝对值等于n就能同时识别两种胜者。这个判断在扫描过程中也安全：只看了一部分格子时，计数绝对值不可能超过已经处理的位置数，更不可能提前达到
n。首次达到n的那条线一定刚被当前非空字符补全，所以直接返回当前字符即可，无需重新遍历这条线。空格不参与任何编码和，只把
hasEmptyGrid置为真。扫描结束仍未发现获胜直线，才根据它返回Pending或Draw。如果中途已经获胜，是否还存在空格都不再影响结果。
解题步骤
- 创建长度为 $n$ 的
rows、cols，并将两个对角线计数初始化为 $0$。- 扫描
(i, j)：遇到空格只记录hasEmptyGrid = true；否则把当前字符的 $1$ 或 $-1$ 累加到对应行列。- 当
i == j时更新主对角线；当i + j == n - 1时更新副对角线。- 任意相关计数的绝对值达到 $n$ 时返回当前字符。扫描结束后，有空格返回
Pending，否则返回Draw。中心格可能同时属于两条对角线，应分别更新两份计数，而不是使用互斥分支。
n == 1时，一个非空格就构成完整直线；全空棋盘则没有胜者，最后返回Pending。
代码实现
// X 记为 1、O 记为 -1；某条线的绝对值达到 n 即出现胜者。
class Solution {
public String tictactoe(String[] board) {
int n = board.length;
int[] rows = new int[n];
int[] cols = new int[n];
int dg = 0;
int udg = 0;
boolean hasEmptyGrid = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char c = board[i].charAt(j);
if (c == ' ') {
hasEmptyGrid = true;
continue;
}
int v = c == 'X' ? 1 : -1;
rows[i] += v;
cols[j] += v;
if (i == j) {
dg += v;
}
if (i + j + 1 == n) {
udg += v;
}
if (Math.abs(rows[i]) == n
|| Math.abs(cols[j]) == n
|| Math.abs(dg) == n
|| Math.abs(udg) == n) {
return String.valueOf(c);
}
}
}
return hasEmptyGrid ? "Pending" : "Draw";
}
}
// X 记为 1、O 记为 -1；某条线的绝对值达到 n 即出现胜者。
func tictactoe(board []string) string {
n := len(board)
rows := make([]int, n)
cols := make([]int, n)
dg, udg := 0, 0
hasEmptyGrid := false
for i, row := range board {
for j, c := range row {
if c == ' ' {
hasEmptyGrid = true
continue
}
v := 1
if c == 'O' {
v = -1
}
rows[i] += v
cols[j] += v
if i == j {
dg += v
}
if i+j == n-1 {
udg += v
}
if abs(rows[i]) == n || abs(cols[j]) == n || abs(dg) == n || abs(udg) == n {
return string(c)
}
}
}
if hasEmptyGrid {
return "Pending"
}
return "Draw"
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$O(n^2)$，每个棋盘格只处理一次。
- 空间复杂度：$O(n)$，行列计数数组各占 $O(n)$；其余变量为常数空间。
关键点总结
[!green]
- 编码和的关键不变量是：长度为 $n$ 的直线和为 $\pm n$，当且仅当整条线属于同一玩家。
- 空格不能参与计数，但要单独记录，用于最终区分
Pending和Draw。- 面试中要主动说明返回优先级：胜者高于棋盘是否仍有空位。
- 如果追问“每次落子后都要判断”，可以只更新该落子所在的行、列和对角线，从而把单次操作降为 $O(1)$。
易错点总结
[!yellow]
- 先看到空格就返回
Pending：后面仍可能发现已经完成的获胜直线，胜负判断优先。- 副对角线条件写错：下标从 $0$ 开始时应满足
i + j == n - 1，不是i + j == n。- 只判断计数等于 $n$：这样只能识别
X；应判断绝对值，才能同时识别和为 $-n$ 的O。- 把空格按
O处理：会伪造负计数，甚至错误判断O获胜。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 348. 设计井字棋 | 中等 | 同样使用行列与对角线计数，原题按每次落子增量更新，本题一次扫描整盘。 |