)
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote对 LeetCode 0348《设计井字棋》的完整技术拆解。这篇中等难度的设计类题目要求在 n×n 棋盘上实现一个判定器支持每落一子即判断是否有玩家获胜并直接给出进阶挑战——能否把每次move()的判定做到比 O(n²) 更快。读完本文你将掌握「计数数组」这一设计模式的本质用四个计数结构行、列、两条对角线把单次落子的胜负判定压缩到常数时间并能将同一套思路迁移到其他棋盘类设计与模拟题中。一、题目概述一个只问结果、不问过程的胜负判定器本题属于标签为设计、数组、哈希表、矩阵、模拟的经典设计类题目收录于仓库题解索引见 docs/00_preface/00_05_solutions_list.md 中的 0348 行。其核心要求如下在 $n \times n$ 的棋盘上实现一个判定井字棋Tic-Tac-Toe胜负的神器判断每一次玩家落子后是否有胜出的玩家。在这个井字棋游戏中会有 $2$ 名玩家他们将轮流在棋盘上放置自己的棋子。而我们要做的就是为这个判定器实现两个核心接口TicTacToe(n)以棋盘边长 $n$ 初始化游戏move(row, col, player)玩家player取值 $1$ 或 $2$在 $(row, col)$ 处落子返回获胜玩家编号若无人获胜则返回 $0$。值得注意的是题目给出的三条强约束假设它们直接决定了实现可以偷懒的程度每一步棋都是在棋盘内的并且只能被放置在一个空的格子里一旦游戏中有一名玩家胜出的话游戏将不能再继续一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子那么他便获得胜利。也就是说我们不需要处理非法落子也不需要处理两人同时满足获胜条件的复杂局面——赢家一旦出现游戏即终止。这让判定器的实现可以专注于最纯粹的一条路径增量统计 → 到达阈值即获胜。数据约束与进阶要求题目的数据范围给出了明确的复杂度天花板$2 \le n \le 10^{3}$棋盘边长最大可达 1000玩家编号固定为 $1$ 或 $2$$0 \le row, col n$坐标保证在棋盘内每次调用move时 $(row, col)$ 都是不同的不会重复落子最多调用move$n^{2}$ 次即棋盘被填满。进阶要求有没有可能将每一步的move()操作优化到比 $O(n^{2})$ 更快这里需要特别澄清一个容易混淆的点棋盘本身只有 $n^{2}$ 个格子落子总数上界就是 $n^{2}$所以比 $O(n^{2})$ 更快指的不是总操作次数而是单次move()的耗时。最朴素的做法是每次落子后重新扫描整张棋盘遍历行、列、对角线单次判定就是 $O(n)$ 甚至 $O(n^{2})$而本文要介绍的计数法能把单次判定降到 O(1)。二、示例推演看懂move()的返回语义先用题目给出的完整示例把接口行为走一遍。给定棋盘边长 $n 3$玩家 1 的棋子符号是X玩家 2 的棋子符号是OTicTacToe toe new TicTacToe(3); toe.move(0, 0, 1); - 函数返回 0 (此时暂时没有玩家赢得这场对决) |X| | | | | | | // 玩家 1 在 (0, 0) 落子。 | | | | toe.move(0, 2, 2); - 函数返回 0 (暂时没有玩家赢得本场比赛) |X| |O| | | | | // 玩家 2 在 (0, 2) 落子。 | | | | toe.move(2, 2, 1); - 函数返回 0 (暂时没有玩家赢得比赛) |X| |O| | | | | // 玩家 1 在 (2, 2) 落子。 | | |X| toe.move(1, 1, 2); - 函数返回 0 (暂没有玩家赢得比赛) |X| |O| | |O| | // 玩家 2 在 (1, 1) 落子。 | | |X| toe.move(2, 0, 1); - 函数返回 0 (暂无玩家赢得比赛) |X| |O| | |O| | // 玩家 1 在 (2, 0) 落子。 |X| |X| toe.move(1, 0, 2); - 函数返回 0 (没有玩家赢得比赛) |X| |O| |O|O| | // 玩家 2 在 (1, 0) 落子. |X| |X| toe.move(2, 1, 1); - 函数返回 1 (此时玩家 1 赢得了该场比赛) |X| |O| |O|O| | // 玩家 1 在 (2, 1) 落子。 |X|X|X|观察最后一步玩家 1 在 $(2, 1)$ 落子后第 2 行下标 2的三个格子 $(2,0),(2,1),(2,2)$ 全部是X此时move()返回1宣告玩家 1 获胜。注意前面若干次落子包括玩家 2 一度在左列占据两子都没有形成连线因此返回值都是0——这就是判定器要捕捉的阈值时刻。三、思路 1计数法——用增量计数替代全盘扫描3.1 核心思想使用计数数组来跟踪每个玩家在每行、每列和两条对角线上的棋子数量避免每次检查整个棋盘。井字棋的获胜条件本质上是某个玩家在某一条线行、列或对角线上凑齐了 $n$ 个棋子。而一条线是否被凑齐不需要每次落子后从头扫描——只要在落子时对该子所在的那几条线做一次增量计数并检查计数是否达到 $n$ 即可。一个格子最多同时属于 4 条线1 条行、1 条列、最多 1 条主对角线、最多 1 条副对角线。因此单次落子只需要更新并检查常数条线这就是 O(1) 的来源。从数据结构设计的角度看这套计数数组本质上是把棋盘状态压缩成了四条线方向上的投影统计。它和仓库教程 docs/03_stack_queue_hash_table/03_06_hash_table.md 中哈希表用键直接定位、以空间换时间的思想同源我们不关心棋盘上每个格子的具体归属只关心每条线上各玩家的计数用常数个数组完成 $O(n^{2})$ 棋盘信息的等效维护。3.2 算法步骤第 1 步初始化创建 $n \times n$ 的棋盘用于记录落子位置便于必要时回放或调试以及用于计数的数据结构rows[i]第 $i$ 行上每个玩家的棋子数量rows[i][0]记玩家 1rows[i][1]记玩家 2cols[j]第 $j$ 列上每个玩家的棋子数量索引语义同上diagonal主对角线满足 $row col$上的棋子数量两个元素分别对应两名玩家anti_diagonal副对角线满足 $row col n - 1$上的棋子数量。第 2 步落子操作在位置 $(row, col)$ 放置玩家player的棋子更新对应的行、列计数rows[row]与cols[col]中该玩家的计数各加 1如果 $(row, col)$ 在主对角线上$row col$更新diagonal如果 $(row, col)$ 在副对角线上$row col n - 1$更新anti_diagonal。第 3 步胜负判断检查当前行、列或对角线是否被当前玩家完全占据如果任一计数达到 $n$则该玩家获胜直接返回该玩家编号否则返回0无人获胜。边界条件说明只有落在对角线上时才会触发对角线计数因此副对角线判定条件row col n - 1与主对角线判定条件row col是相互独立的两者可能同时成立当 $n$ 为奇数时正中央的格子同时属于两条对角线因为题目保证每次move的 $(row, col)$ 都不同计数数组不会重复累加同一格无需考虑覆盖落子的情况获胜检查只看当前落子玩家的四条线计数不需要检查对方——若对方此前已获胜游戏早已终止规则 2不会出现双方同时到达阈值的调用场景。3.3 完整代码实现class TicTacToe: def __init__(self, n: int): 初始化井字棋游戏 :param n: 棋盘大小 n x n self.n n # 初始化棋盘 self.board [[0 for _ in range(n)] for _ in range(n)] # 计数数组跟踪每个玩家在每行、每列的棋子数量 # rows[i][player] 表示第 i 行上玩家 player 的棋子数量 self.rows [[0, 0] for _ in range(n)] # 索引 0 和 1 分别对应玩家 1 和 2 self.cols [[0, 0] for _ in range(n)] # 索引 0 和 1 分别对应玩家 1 和 2 # 对角线计数 self.diagonal [0, 0] # 主对角线 (i j) self.anti_diagonal [0, 0] # 副对角线 (i j n - 1) def move(self, row: int, col: int, player: int) - int: 玩家在指定位置落子 :param row: 行索引 :param col: 列索引 :param player: 玩家编号 (1 或 2) :return: 获胜玩家编号如果无人获胜返回 0 # 将玩家编号转换为数组索引 (1 - 0, 2 - 1) player_idx player - 1 # 在棋盘上放置棋子 self.board[row][col] player # 更新行计数 self.rows[row][player_idx] 1 # 更新列计数 self.cols[col][player_idx] 1 # 更新主对角线计数 (row col) if row col: self.diagonal[player_idx] 1 # 更新副对角线计数 (row col n - 1) if row col self.n - 1: self.anti_diagonal[player_idx] 1 # 检查是否获胜 # 如果当前行、列或任一对角线被当前玩家完全占据则获胜 if (self.rows[row][player_idx] self.n or self.cols[col][player_idx] self.n or self.diagonal[player_idx] self.n or self.anti_diagonal[player_idx] self.n): return player return 0 # 无人获胜 # Your TicTacToe object will be instantiated and called as such: # obj TicTacToe(n) # param_1 obj.move(row,col,player)3.4 代码逐段解析1玩家编号与数组索引的映射player_idx player - 1把外部语义玩家 1 / 玩家 2映射为数组下标0 / 1。这是设计类题目的常见手法让计数数组的每个元素本身就是一个长度为 2 的小数组[0]存玩家 1、[1]存玩家 2从而一套结构同时服务两名玩家避免为每人复制一份行/列/对角线统计。2棋盘数组self.board的作用从胜负判定的纯逻辑看board并非必需——计数数组已包含全部判定信息。但保留它的价值在于一是忠实还原题目在棋盘上放置棋子的语义便于调试时打印局面二是为后续可能的扩展如查询某个位置被谁占据留下余地。如果追求极致的内存优化可以去掉board此时空间开销进一步收敛到四个计数结构。3获胜检查的短路语义if (self.rows[row][player_idx] self.n or self.cols[col][player_idx] self.n or self.diagonal[player_idx] self.n or self.anti_diagonal[player_idx] self.n): return player四个条件用or连接一旦命中即返回获胜玩家。注意这里只需要检查当前落子所在的 4 条线其他行/列/对角线上没有新增棋子计数不可能在这次调用中到达阈值。这正是把单次判定从扫全盘降为查 4 条线的关键。4主/副对角线判定公式的几何意义主对角线$(0,0), (1,1), \dots, (n-1,n-1)$特征是行号等于列号即 $row col$副对角线$(0,n-1), (1,n-2), \dots, (n-1,0)$特征是行号与列号之和恒为 $n-1$即 $row col n - 1$。两条对角线判定互相独立且一个格子最多同时满足两者$n$ 为奇数时的中心格如 $n3$ 时的 $(1,1)$。代码中两个if不是elif的关系正是为了正确处理这种一个格子同时属于两条对角线的边界情形。3.5 复杂度分析时间复杂度$O(1)$。每次move操作只需要更新计数数组行、列以及最多两条对角线共 4 次自增并检查胜负4 个常数比较时间复杂度为常数与棋盘边长 $n$ 无关。相比每次落子后扫描整张棋盘的朴素方案单次 $O(n^{2})$且每次都要遍历全部行、列、对角线计数法在 $n 1000$ 的极限规模下性能提升显著。空间复杂度$O(n^{2})$。需要 $O(n^{2})$ 空间存储棋盘board$O(n)$ 空间存储行、列计数数组两个 $n \times 2$ 的数组$O(1)$ 空间存储两条对角线计数总体为 $O(n^{2})$。如果从空间上进一步收紧——移除board数组——则空间可降到 $O(n)$行、列计数数组各 $2n$ 个整数 4 个对角线计数。这也是面试中常被追问的优化点用空间换时间的计数思想本身也可以反过来压缩空间。四、思路对比为什么计数法是设计类题目的正解把本题与朴素模拟放在一起对比可以更清晰地看到设计意图方案单次move()耗时实现要点适用场景朴素模拟落子后扫描全盘$O(n^{2})$遍历 $n$ 行 $n$ 列 2 条对角线维护棋盘矩阵每次落子后重新检查所有方向棋盘小、调用次数少计数法$O(1)$维护行/列/对角线计数落子时增量更新并只查 4 条线$n$ 大、调用频繁适合作为判定器被反复调用从设计器/判定器这类题型的本质来看move()会被高频调用最多 $n^{2}$ 次把单次调用的成本压到常数正是设计类题目考察的核心能力。这种增量维护统计量、阈值判定的模式与仓库题解中的另一道设计题 0346. 数据流中的移动平均值 有异曲同工之处后者同样维护一个滑动窗口的累计值来避免每次重新求和。五、仓库内的井字棋姊妹题从设计器到判状态的完整拼图井字棋在 LeetCode 中是一个成体系的题目族仓库题解目录中至少收录了以下三题恰好覆盖了井字棋问题的三个不同侧面可以串联起来对比学习11275. 找出井字棋的获胜者简单数组/哈希表/矩阵/模拟固定 $3 \times 3$ 棋盘给定完整落子序列moves要求判断最终结果是 A 胜、B 胜、平局还是未结束。它的解法是离线模拟按顺序落子、每步枚举 8 种赢法3 行 3 列 2 条对角线检查棋盘满且无人获胜则为Draw否则为Pending。由于棋盘固定为 $3 \times 3$赢法数量是常数 8单步检查同样是常数时间。它与本题的差异在于本题是在线增量判定每次调用只给一步要求即时返回而 1275 题是给定全序列后一次性判定。20794. 有效的井字游戏中等数组/矩阵给定一个 $3 \times 3$ 的终局棋盘状态判断该状态在合法游戏过程中是否可能出现。它的约束条件X先手、轮流落子、获胜即止与本题的规则假设几乎完全一致但考察方向相反本题假设每一步都合法、只需判定胜负0794 题则反过来——给定任意状态反推其合法性X与O的数量关系、胜者唯一性、获胜步数与棋子数的匹配关系。两道题放在一起恰好构成了正向推演与反向校验的完整闭环。30348. 设计井字棋本题中等设计/数组/哈希表/矩阵/模拟在不固定 $n$ 的通用棋盘上设计判定器强调增量计数与常数时间判定。三题难度递进、侧重点互补是理解模拟 / 设计 / 状态校验三种题型差异的绝佳组合。此外仓库的 docs/00_preface/00_05_solutions_list.md 汇总了全部题解清单可按编号快速定位同类题目docs/00_preface/00_06_categories_list.md 则按标签分类索引便于按设计标签批量刷题。六、小结与举一反三本文的核心结论可以浓缩为三点计数法把全盘扫描变成增量统计井字棋胜负 某条线计数达到 $n$而一次落子最多影响 4 条线因此单次判定天然可以做到 $O(1)$四个计数结构各司其职行、列各一个长度为 $n$ 的计数数组两条对角线各一个计数玩家编号通过player - 1映射为数组下标一套结构服务两名玩家空间与时间可以权衡保留board便于调试与语义完整空间 $O(n^{2})$删除board后空间可压缩到 $O(n)$判定逻辑完全不受影响。当你再遇到设计某某判定器/计数器类题目如棋盘、数据流、限流器等时可以优先思考哪些信息需要全量保存哪些信息可以用增量统计量替代一旦找到阈值即答案的判定结构O(1) 的解法往往就呼之欲出了。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 1275. Find Winner on a Tic Tac Toe Game井字棋胜负判定的 Go 模拟解法LeetCode 1275. Find Winner on a Tic Tac Toe Game井字棋胜负判定的 Go 模拟解法 本篇技术指南以 LeetCo示例工程Ventoy 完整指南3 步做出能直接启动所有系统镜像的 U 盘Ventoy 完整指南3 步做出能直接启动所有系统镜像的 U 盘 你刚下完 Win11 的 ISO想装到同事的旧电脑上可你那个装着 Ubuntu 镜像的操作系统固件开发工具剑指 Offer 43 逐位计数法详解O(log n) 统计 1n 中 1 的出现次数LeetCode-Book 三语言实现剑指 Offer 43 逐位计数法详解O log n 统计 1n 中 1 的出现次数LeetCode Book 三语言实现 本文基于《LeetCode示例工程上一篇APNG Studio 实战在 GitHub Copilot 画布中制作、预览与导出 Animated PNGAPNG下一篇PaddleOCR 模型微调实战基于 PP-OCRv3 检测与识别模型的垂类场景精度提升指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
