LeetCode 348. 设计井字棋

2026-03-28 HGNULB 约 10 分钟

文章信息 2 个分类 5 个标签

分类

LeetCode 中等

题目描述

✅ 348. 设计井字棋

题意分析

题目目标：设计一个 $n \times n$ 的井字棋，move(row, col, player) 表示某位玩家在指定格子落子，返回 0 表示尚无人获胜、返回 1 或 2 表示该玩家此手取胜。题目保证每次落子的位置都是空的，且落子合法。

核心约束：题面直接写着「你能否在每次 move 都是 $O(1)$ 的情况下完成」。这句话把「落子后重扫一遍棋盘」的 $O(n)$ 甚至 $O(n^2)$ 做法直接判掉了，也把整题的考点从模拟变成了增量维护：与其在需要时重算，不如在每次变更时把结论顺手更新掉。

边界处理：一个格子可能同时属于行、列、主对角线、副对角线四条获胜线（比如 $n$ 为奇数时的正中央）；主副对角线在 $n$ 为奇数时相交于中心，两个计数器必须彼此独立；$n = 1$ 时唯一那格同时是行、列、主对角、副对角，一手即胜。

实现取舍：可以为每位玩家开四组计数器（行、列、主对角、副对角），也可以用一个「正负号」的技巧把两位玩家合并到同一组计数器里（一方 +1、另一方 -1，绝对值达到 $n$ 即胜）。前者语义直白、扩展到多人也不变形，后者更省内存但可读性差一档。本文用前者，并把四类计数器压进同一个一维数组里，靠下标区间区分。

解法：哈希表统计状态

核心思路

暴力做法是每次落子后扫描该行、该列以及两条对角线，看是否已经连成 $n$ 个，单次 move 是 $O(n)$。更差的写法是整盘重扫，$O(n^2)$。瓶颈很明显：每次都在重复计算大量没有变化的信息——这一手只影响它所在的至多四条线，其余的线一格都没动。

关键观察：获胜条件是「某位玩家在某条线上占满 $n$ 格」，而「占满」这件事只需要一个计数就能判定，完全不必知道具体是哪些格子。因为题目保证落子位置为空，同一格不会被重复计数，所以「某玩家在某条线上的落子数」这个计数器只增不减，达到 $n$ 就等价于占满整条线。

于是状态定义写死为：cnt[p][t] 表示玩家 p（0 或 1）在第 t 条线上已经落了多少子。线的编号约定为——t ∈ [0, n) 是第 t 行，t ∈ [n, 2n) 是第 t - n 列，t = 2n 是主对角线（row == col），t = 2n + 1 是副对角线（row + col == n - 1）。这样两位玩家各需 $2n + 2$ 个计数器，用一个 int[2][2n + 2] 一次开好。

不变量是：任意时刻，cnt[p][t] 恰好等于玩家 p 在线 t 上已占据的格子数。每次落子只会让至多四个计数器各加一（行、列必加，两条对角线视位置而定），因此维护成本是常数；胜负判定只需检查这四个计数器里有没有达到 $n$ 的，同样是常数。

要特别注意主副对角线是两个独立的计数器而不是一个。$n$ 为奇数时中心格同时落在两条对角线上，会让两个计数器同时加一，这是正确的；如果误合并成一个计数器，中心格会被算两次，可能提前误判获胜。

解题步骤

第一步：构造函数里保存 n，并开辟 cnt = new int[2][2 * n + 2]。 为什么第一维是 2：两位玩家的进度必须分开统计，混在一起会把双方的落子累加成同一条线的进度。为什么第二维是 $2n + 2$：$n$ 行 + $n$ 列 + 2 条对角线，正好占满。

第二步：move 里先取出该玩家的计数数组 cur = cnt[player - 1]。 为什么减一：题目的玩家编号是 1 和 2，而数组下标从 0 开始，这个偏移必须在唯一的地方完成，散落到多处就容易漏。

第三步：cur[row]++ 与 cur[n + col]++。 为什么无条件加：任何一格必定属于且只属于一行一列，这两个计数器每手都要更新。为什么列的下标要加 n：行和列共用同一个数组，用 $[0, n)$ 和 $[n, 2n)$ 两段区间区分，避免开两个数组。

第四步：row == col 时 cur[2n]++，row + col == n - 1 时 cur[2n + 1]++。 为什么用两个独立的 if 而不是 else if：$n$ 为奇数时中心格两个条件同时成立，必须两个计数器都加；写成 else if 会漏掉其中一条对角线的进度。

第五步：检查这四个计数器中是否有任何一个等于 n，是则返回 player，否则返回 0。 为什么只检查这四个：其余线本手没有任何变化，若它们此前已经达到 $n$，游戏早就结束了，不可能轮到现在才发现。为什么用 == 而不是 >=：计数器只增不减且一旦达到 $n$ 就立刻返回，正常流程下不会越过 $n$；用 >= 也对，但 == 更能表达「恰好在这一手连成」的语义。

以 $n = 3$，依次执行 move(0,0,1)、move(0,2,2)、move(2,2,1)、move(1,1,2)、move(2,0,1)、move(1,0,2)、move(2,1,1) 走一遍。约定下标：行 0~~2，列 3~~5，主对角 6，副对角 7。

move(0,0,1)：玩家 1 的数组。cur[0] 变 1（第 0 行），cur[3] 变 1（第 0 列），row == col 成立，cur[6] 变 1（主对角）；row + col = 0 ≠ 2，副对角不动。四个值中最大是 1，不等于 3，返回 0。

move(0,2,2)：玩家 2 的数组。cur[0] 变 1，cur[5] 变 1；0 ≠ 2 主对角不动；0 + 2 = 2 = n - 1，cur[7] 变 1。返回 0。

move(2,2,1)：玩家 1。cur[2] 变 1，cur[5] 变 1；2 == 2，cur[6] 变 2——玩家 1 的主对角已有两子；2 + 2 = 4 ≠ 2。最大值 2，返回 0。

move(1,1,2)：玩家 2。cur[1] 变 1，cur[4] 变 1；1 == 1，cur[6] 变 1；同时 1 + 1 = 2 = n - 1，cur[7] 变 2。这一步就是中心格同时命中两条对角线的现场：如果第四步写成 else if，副对角的 cur[7] 就会停在 1，玩家 2 后续的副对角进度全部失真。返回 0。

move(2,0,1)：玩家 1。cur[2] 变 2，cur[3] 变 2；2 ≠ 0；2 + 0 = 2，cur[7] 变 1。最大值 2，返回 0。

move(1,0,2)：玩家 2。cur[1] 变 2，cur[3] 变 1；两条对角线都不命中。最大值 2，返回 0。

move(2,1,1)：玩家 1。cur[2] 变 3 —— 第 2 行三格齐了；cur[4] 变 1；对角线不命中。检查发现 cur[2] == 3 == n，返回 1。对照棋盘，玩家 1 确实占满了第 2 行的 (2,0)、(2,1)、(2,2)，与期望一致。

代码实现

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)$。凭什么：构造要把 $2 \times (2n + 2)$ 个计数器清零；move 里只有至多四次自增和四次比较，全部与 $n$ 无关，这正是题面进阶要求的目标。

空间复杂度：$O(n)$。凭什么：只存 $2(2n + 2)$ 个计数器，完全没有保存棋盘本身——因为判定获胜不需要知道每个格子的归属，只需要每条线上的计数。

关键点总结

设计题要求 $O(1)$ 时，思路一定是「增量维护结论」而不是「按需重算」。 认出「获胜 = 某条线计数达标」这层等价，是把 $O(n)$ 压到 $O(1)$ 的唯一入口。

只保存判定所需的聚合量，别保存原始数据。 本题连棋盘都不用开，空间从 $O(n^2)$ 降到 $O(n)$，这是设计题里很典型的加分点。

多类计数器压进一个数组时，用下标区间划分并把偏移写在唯一的地方。 row、n + col、2n、2n + 1 这套编号可以直接迁移到任何「行/列/对角线」类题目。

两条对角线的判断必须是两个独立的 if。 奇数阶棋盘的中心格同时命中两条线，else if 会静默丢掉一条线的进度，而且要到很后面才暴露。

玩家编号到数组下标的映射只做一次。 player - 1 分散在多处是这类题最常见的低级错误来源。

面试视角：先复述进阶要求「每次 move 要 $O(1)$」以表明抓住了考点，再讲「只需计数不需棋盘」的核心等价，然后写代码。写完主动提两个延伸：一是可以用「玩家 1 记 +1、玩家 2 记 -1、绝对值达 $n$ 即胜」把空间再砍一半；二是如果要支持 undo 或多于两名玩家，计数器方案天然可扩展（自减、加一维），而正负号方案就不行了。

易错点总结

错误写法：两条对角线的判断写成 if (row == col) {...} else if (row + col == n - 1) {...} → 用例 $n = 3$ 时执行 move(1,1,2)，中心格只让主对角计数加一，副对角停在原值；后续玩家 2 再下 (0,2)、(2,0) 时副对角计数只到 2，明明已经连成三子却返回 0。

错误写法：主副对角线共用一个计数器 → 用例 $n = 3$ 时玩家 2 依次下 (0,0)、(1,1)、(0,2)，共用计数器被加到 4（其中中心格贡献 2），中途在 (1,1) 之后就达到 3 而误报玩家 2 获胜。

错误写法：cnt 只开一维，两位玩家共用 → 用例 $n = 3$ 时玩家 1 下 (0,0)、玩家 2 下 (0,1)、玩家 1 下 (0,2)，第 0 行的计数被累加到 3，误判最后落子的玩家 1 获胜，而实际这一行是混合的。

错误写法：忘记 player - 1，直接用 cnt[player] → 用例 player = 2 时数组下标越界抛异常；player = 1 时又与 player = 2 的数据混淆。

错误写法：列的计数器不加偏移，写成 cur[col]++ → 用例 $n = 3$ 时玩家 1 下 (0,0)、(1,0)、(2,0)（第 0 列三子），行计数分别落在下标 0、1、2，列计数也落在下标 0、0、0，下标 0 被加了 4 次，在第二手之后就误报获胜。

错误写法：副对角判断写成 row + col == n → 用例 $n = 3$ 时真正的副对角是 (0,2)、(1,1)、(2,0)（和为 2），条件却要求和为 3，副对角永远统计不到，玩家连成副对角时返回 0。

错误写法：判定时检查全部 $2n + 2$ 个计数器 → 功能正确但单次 move 退化为 $O(n)$，不满足题目进阶要求，属于「答案对但没答到点上」。

错误写法：先判定再自增 → 用例 $n = 1$ 时 move(0,0,1)，判定时计数还是 0，返回 0，而正确答案是玩家 1 立即获胜。

错误写法：数组大小开成 2 * n 忘了给两条对角线留位置 → 用例任意 $n$，访问 cur[2n] 立刻越界。

错误写法：用 >= 判定但计数器允许重复落子累加 → 若题目变体不再保证落子位置为空，同一格重复落子会让计数虚高，>= 会掩盖这个问题；此时必须额外维护棋盘去重。

相似题目

题目	难度	考察点
36. 有效的数独	中等	同样按行/列/宫维护计数，但判定的是「是否重复」而非「是否占满」，且要多一套 3×3 宫的编号
289. 生命游戏	中等	需要原地保存棋盘并同时读写，靠位标记区分新旧状态，无法只用聚合量代替棋盘
933. 最近的请求次数	简单	同为「每次调用 $O(1)$ 增量维护」的设计题，但维护的是滑动时间窗而非静态的线