LeetCode 348. 设计井字棋

约 4 分钟
文章信息 3 个分类 5 个标签
分类
LeetCode 中等 会员题
标签
数组 哈希表 矩阵 设计 模拟

题目描述

✅ 348. 设计井字棋

题意分析

在 n × n 棋盘上，两位玩家交替落子。每次合法落子后，判断是否有玩家占满某一整行、整列、主对角线或副对角线，获胜时返回玩家编号，否则返回 0。

本篇沿用落子合法、不重复占用格子的约定，重点是在每次 move 中用常数时间判定胜负。判断的是整条长度为 n 的线，不是任意方向上出现若干相邻棋子。

解法：分别累计行、列和对角线

核心思路

[!blue]

一次落子只会增加所在行、所在列，以及可能属于的两条对角线中的棋子数。其他行列没有变化，因此可以在落子时更新少数计数，而不必每次重新扫描整个棋盘。

为两个玩家分别维护一组计数，每组共 2n + 2 项：前 n 项保存各行，接下来的 n 项保存各列，最后两项保存主对角线和副对角线。用 player - 1 选择当前玩家的数据，避免两人的棋子被混到同一个数量中。

由于合法落子不会重复占据同一格，而每条线恰好只有 n 个格子，当前玩家的某条线计数达到 n，就意味着这条线全部由他占据，足以判胜。计数未到 n 则不能宣告这一条线完成。

每次固定更新行和列。row == col 时还更新主对角线，row + col == n - 1 时更新副对角线；两条条件必须分别判断，中心格可能同时属于两条线。更新后检查当前行、当前列与两个对角计数即可，全程只有固定数量的操作。

合法调用前提使这里无需额外棋盘去记录每格占用情况；所维护的数据只承担各条线的累计与胜负检测。

解题步骤

  1. 构造两个玩家的计数数组，每组长度为 2n + 2，初始为零。
  2. 当前玩家的行计数 row 与列计数 n + col 分别加一。
  3. 落在主对角线时增加下标 2n，落在副对角线时增加下标 2n + 1。
  4. 当前行、当前列或任一对角计数达到 n，返回当前玩家编号；否则返回 0。

代码实现

class TicTacToe {
    private int n;
    private int[][] cnt;

    public TicTacToe(int n) {
        this.n = n;
        cnt = new int[2][(n << 1) + 2];
    }

    public int move(int row, int col, int player) {
        int[] cur = cnt[player - 1];

        ++cur[row];
        ++cur[n + col];

        if (row == col) {
            ++cur[n << 1];
        }

        if (row + col == n - 1) {
            ++cur[n << 1 | 1];
        }

        if (cur[row] == n || cur[n + col] == n || cur[n << 1] == n || cur[n << 1 | 1] == n) {
            return player;
        }

        return 0;
    }
}

type TicTacToe struct {
    n   int
    cnt [][]int
}

func Constructor(n int) TicTacToe {
    cnt := make([][]int, 2)
    for i := range cnt {
        cnt[i] = make([]int, (n<<1)+2)
    }
    return TicTacToe{n, cnt}
}

func (this *TicTacToe) Move(row int, col int, player int) int {
    cur := this.cnt[player-1]
    cur[row]++
    cur[this.n+col]++
    if row == col {
        cur[this.n<<1]++
    }
    if row+col == this.n-1 {
        cur[this.n<<1|1]++
    }
    if cur[row] == this.n || cur[this.n+col] == this.n || cur[this.n<<1] == this.n || cur[this.n<<1|1] == this.n {
        return player
    }
    return 0
}

复杂度分析

  • 时间复杂度：构造时初始化 $O(n)$ 个计数；单次 move 只更新并比较固定数量的值，为 $O(1)$。
  • 空间复杂度：$O(n)$，两个玩家各保存 2n + 2 个计数。

关键点总结

[!green]

  • 增量维护受当前落子影响的线，避免每轮重复读取全部棋盘。
  • 两位玩家分开计数，达到整条线长度时才表示同一玩家占满。
  • 两条对角线独立更新，不能因为命中一条就跳过另一条。

易错点总结

[!yellow]

  • 行与列使用同一段下标，会让不同线的棋子数量相互污染。
  • 忘记玩家编号从 1 开始，直接作为数组下标会选错玩家或越界。
  • 两个对角条件写成 if / else if，会漏记同时位于两条对角线的中心格。
  • 只判断是否在网格外缘，不能确定是否属于副对角线，后者要满足行列下标之和为 n - 1。
  • 在重复落子或其他非法调用下直接使用这套计数，数量可能超过真实占据格数；本文依照既有合法调用约定。

相似题目

题目 难度 关联与区别
面试题 16.04. 井字游戏 中等 原题读取完整棋盘后检查结果，本题维护增量计数来支持每次落子的常数时间查询。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/65946966
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！