LeetCode 面试题 16.04. 井字游戏

约 5 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数组 矩阵 计数
目录

题目描述

✅ 面试题 16.04. 井字游戏

题意分析

题目目标：判断一个已经进行到某一步的 $n \times n$ 井字棋棋盘，当前是 X 获胜、O 获胜、仍可继续的 Pending，还是已经下满但无人获胜的 Draw。
核心约束：获胜要求某一整行、整列或两条对角线上的字符完全相同；棋盘中的空格表示尚未落子。
返回优先级：必须先判断胜负。即使棋盘仍有空格，只要已经连成一条线，也应返回获胜方，而不是 Pending。
朴素瓶颈：分别复制并比较所有候选直线会产生重复代码。把 X 记为 $1$、O 记为 $-1$，一次扫描即可统一维护所有直线的计数。

解法：行列与对角线计数

核心思路

用 rows[i] 和 cols[j] 分别记录第 $i$ 行、第 $j$ 列的编码和，同时用 diagonal、antiDiagonal 记录两条对角线。
对非空格位置，X 贡献 $1$，O 贡献 $-1$。一条长度为 $n$ 的线只有全是 X 时和为 $n$，全是 O 时和为 $-n$，因此绝对值等于 $n$ 就意味着当前字符获胜。
这个不变量把行、列和对角线统一成同一种判断，扫描过程中还可以在发现胜者时立即返回。

解题步骤

  • 创建长度为 $n$ 的 rows、cols，并将两个对角线计数初始化为 $0$。
  • 扫描 (i, j)：遇到空格只记录 hasEmptyGrid = true；否则把当前字符的 $1$ 或 $-1$ 累加到对应行列。
  • 当 i == j 时更新主对角线；当 i + j == n - 1 时更新副对角线。
  • 任意相关计数的绝对值达到 $n$ 时返回当前字符。扫描结束后，有空格返回 Pending，否则返回 Draw。

例如棋盘 ['O X', ' XO', 'X O'] 的副对角线依次累加为 $1,2,3$。虽然棋盘还有空格，但 X 已经获胜，必须返回 X。

代码实现

// 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, 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)$；其余变量为常数空间。

关键点总结

  • 编码和的关键不变量是：长度为 $n$ 的直线和为 $\pm n$，当且仅当整条线属于同一玩家。
  • 空格不能参与计数，但要单独记录，用于最终区分 Pending 和 Draw。
  • 面试中要主动说明返回优先级：胜者高于棋盘是否仍有空位。
  • 如果追问“每次落子后都要判断”，可以只更新该落子所在的行、列和对角线，从而把单次操作降为 $O(1)$。

易错点总结

  • 先看到空格就返回 Pending：如 ['O X', ' XO', 'X O'] 仍有空格，但 X 已通过副对角线获胜。
  • 副对角线条件写错：下标从 $0$ 开始时应满足 i + j == n - 1，不是 i + j == n。
  • 只判断计数等于 $n$：这样只能识别 X；应判断绝对值，才能同时识别和为 $-n$ 的 O。
  • 把空格按 O 处理：会伪造负计数，甚至错误判断 O 获胜。

相似题目

题目 难度 考察点
1275. 找出井字棋的获胜者 简单 落子状态模拟
348. 设计井字棋 中等 动态计数
794. 有效的井字游戏 中等 状态合法性