leetcode 多语言解题仓库中的 Tic-Tac-Toe 设计从行列对角线扫描到 O(1) 累计计数判胜【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕 leetcode 解题仓库中的 design-tic-tac-toe.md 展开完整讲解 LeetCode 348「Design Tic-Tac-Toe」的两种经典实现基于棋盘聚焦检查的 O(n) 方案与基于 ±1 累计计数的 O(1) 方案。读完本文你将理解两种方案各自的算法动机、逐步实现细节与复杂度差异并掌握井字棋类题目中最容易踩中的三个陷阱。题目定义与约束题目要求实现一个TicTacToe类支持在 n×n 棋盘上进行游戏TicTacToe(int n)初始化一个 n×n 的空棋盘int move(int row, int col, int player)表示编号为 player1 或 2的玩家在位置 (row, col) 落子返回当前胜者1 或 2若无胜者则返回 0。题目保证每次 move 的坐标都合法且该位置仍为空、两位玩家轮流落子、一旦有人达成整行/整列/整条对角线获胜游戏立即结束因此 move 的调用次数不超过 n²。本文后续所有代码均来自仓库文档 design-tic-tac-toe.md覆盖 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言下文为便于讲解完整展示 Python 与 Java 两个版本其余语言在同一文档中以相同逻辑给出。前置知识文档在正文前列出了三个前置知识点它们正是两种方案共用的技术底座二维数组2D Arrays创建并遍历矩阵来表示棋盘对角线遍历Diagonal Traversal识别主对角线row col与反对角线col n - row - 1两种位置模式计数技巧Counting Techniques用运行累计和running sum高效跟踪对局状态这是第二种方案的核心。方案一优化暴力——只检查本次落子影响的行、列与对角线直觉在井字棋中玩家通过填满一整行、一整列或一条对角线获胜。每次落子之后我们只需要判断这一手是否创造了获胜条件而不是扫描整个棋盘。具体地只检查该落子所在的行与列且仅当落子点位于主对角线或反对角线上时才检查对应对角线。算法步骤初始化一个 n×n 棋盘所有格子设为0玩家在 (row, col) 落子时把该格标记为 player 编号通过以下四路检查判断该玩家是否获胜检查当前行的所有格子是否都属于该玩家检查当前列的所有格子是否都属于该玩家若落子在主对角线上row col检查主对角线所有格子若落子在反对角线上col n - row - 1检查反对角线所有格子任一条获胜条件满足则返回 player否则返回0。Python 实现class TicTacToe: def __init__(self, n: int): self.board [[0] * n for _ in range(n)] self.n n def move(self, row: int, col: int, player: int) - int: self.board[row][col] player # check if the player wins if ((self._check_row(row, player)) or (self._check_column(col, player)) or (row col and self._check_diagonal(player)) or (col self.n - row - 1 and self._check_anti_diagonal(player))): return player # No one wins return 0 def _check_diagonal(self, player: int) - bool: for row in range(self.n): if self.board[row][row] ! player: return False return True def _check_anti_diagonal(self, player: int) - bool: for row in range(self.n): if self.board[row][self.n - row - 1] ! player: return False return True def _check_column(self, col: int, player: int) - bool: for row in range(self.n): if self.board[row][col] ! player: return False return True def _check_row(self, row: int, player: int) - bool: for col in range(self.n): if self.board[row][col] ! player: return False return TrueJava 实现class TicTacToe { private int[][] board; private int n; public TicTacToe(int n) { board new int[n][n]; this.n n; } public int move(int row, int col, int player) { board[row][col] player; // check if the player wins if ((checkRow(row, player)) || (checkColumn(col, player)) || (row col checkDiagonal(player)) || (col n - row - 1 checkAntiDiagonal(player))) { return player; } // No one wins return 0; } private boolean checkDiagonal(int player) { for (int row 0; row n; row) { if (board[row][row] ! player) { return false; } } return true; } private boolean checkAntiDiagonal(int player) { for (int row 0; row n; row) { if (board[row][n - row - 1] ! player) { return false; } } return true; } private boolean checkColumn(int col, int player) { for (int row 0; row n; row) { if (board[row][col] ! player) { return false; } } return true; } private boolean checkRow(int row, int player) { for (int col 0; col n; col) { if (board[row][col] ! player) { return false; } } return true; } }复杂度分析时间复杂度O(n)。每次 move 最多检查一行 一列 至多两条对角线每条线长 n借助短路求值short-circuit实际开销往往更低空间复杂度O(n²)用于存储完整棋盘。这个方案的本质是「用空间换检查范围」既然棋盘已完整落盘判胜就是一次针对性的线性扫描。它逻辑直观、易于调试适合需要保留完整棋盘状态例如要回显棋面、支持悔棋的场景。方案二±1 累计计数将每次判胜压缩到 O(1)直觉与其存储整个棋盘、每次落子后再扫描整行整列不如维护累计计数玩家 1 记1玩家 2 记-1。对每一行、每一列以及两条对角线分别维护一个累加和。当某条线的累计和达到n或-n时意味着这条线上的 n 个格子全部属于同一玩家对局立刻分出胜负。这一编码的巧妙之处在于两个玩家共用同一组计数器。如果一行里混入了对手的棋子累计和的绝对值会偏小例如 3×3 棋盘上 2 个玩家 1 的子和 1 个玩家 2 的子和为2 - 1 1永远不会触达 ±n 阈值从而无需区分「是谁的 n 子」也无需保存具体落子内容。算法步骤初始化两个长度为 n 的数组rows、cols以及主对角线diagonal、反对角线antiDiagonal两个变量全部为 0玩家在 (row, col) 落子时将 player 换算为1玩家 1或-1玩家 2把该值累加到对应的行计数器与列计数器若落子在主对角线上row col累加主对角线计数器若落子在反对角线上col n - row - 1累加反对角线计数器若任一计数器的绝对值等于 n返回当前 player 编号否则返回0。Python 实现class TicTacToe: def __init__(self, n: int): self.rows [0] * n self.cols [0] * n self.diagonal 0 self.antiDiagonal 0 def move(self, row: int, col: int, player: int) - int: currentPlayer 1 if player 1 else -1 # update currentPlayer in rows and cols arrays self.rows[row] currentPlayer self.cols[col] currentPlayer # update diagonal if row col: self.diagonal currentPlayer # update anti diagonal if col (len(self.cols) - row - 1): self.antiDiagonal currentPlayer n len(self.rows) # check if the current player wins if (abs(self.rows[row]) n or abs(self.cols[col]) n or abs(self.diagonal) n or abs(self.antiDiagonal) n): return player # No one wins return 0Java 实现class TicTacToe { int[] rows; int[] cols; int diagonal; int antiDiagonal; public TicTacToe(int n) { rows new int[n]; cols new int[n]; } public int move(int row, int col, int player) { int currentPlayer (player 1) ? 1 : -1; // update currentPlayer in rows and cols arrays rows[row] currentPlayer; cols[col] currentPlayer; // update diagonal if (row col) { diagonal currentPlayer; } // update anti diagonal if (col (cols.length - row - 1)) { antiDiagonal currentPlayer; } int n rows.length; // check if the current player wins if (Math.abs(rows[row]) n || Math.abs(cols[col]) n || Math.abs(diagonal) n || Math.abs(antiDiagonal) n) { return player; } // No one wins return 0; } }一个 3×3 对局的执行追踪以下按 LeetCode 官方示例顺序推演方案二的计数器状态帮助验证正确性轮次move(row, col, player)更新动作判定结果1(0, 0, 1)rows[0]1, cols[0]1, diagonal102(0, 2, 2)rows[0]0, cols[2]-1, antiDiagonal-103(2, 0, 1)rows[2]1, cols[0]2, diagonal204(1, 1, 2)rows[1]-1, cols[1]-1, diagonal1, antiDiagonal-205(2, 2, 1)rows[2]2, cols[2]0, diagonal31玩家 1 主对角线三连可以看到第 5 手落子后abs(diagonal) n 3判定玩家 1 获胜——整个过程没有任何一次对棋盘的遍历。复杂度分析时间复杂度O(1)。每次 move 只做常数次加法与四次绝对值比较开销与 n 无关空间复杂度O(n)。只需 n 个行计数器与 n 个列计数器两条对角线各用一个标量。常见陷阱文档单独用一节列举了三个高频错误逐一对照代码理解陷阱一反对角线条件写错差一错误判断某格子是否在反对角线上正确条件是col n - row - 1而不是row col n。后者把偏移量写偏了一格它对应的是右下方那条越界的线# Wrong if row col n: # Off by one error self.antiDiagonal currentPlayer # Correct if col n - row - 1: self.antiDiagonal currentPlayer可以验证一下 3×3 棋盘反对角线三格为 (0,2)、(1,1)、(2,0)它们的row col都等于 2 即n - 1所以条件必须是row col n - 1等价于col n - row - 1。陷阱二奇数棋盘的中心格同时属于两条对角线在 3×3 这类奇数棋盘上中心格 (1,1) 同时落在主对角线与反对角线上。若只在两个if里做二选一例如写成if/elif中心落子时就会漏更新其中一个计数器导致沿另一条对角线的三连无法被检出。两个判断必须独立执行# The center cell (1,1) in a 3x3 board satisfies BOTH conditions: # row col (main diagonal) # col n - row - 1 (anti-diagonal) # Both counters must be updated陷阱三为两个玩家各维护一套计数器一种常见但低效的做法是给玩家 1、玩家 2 分别维护rows_p1、rows_p2两套计数数组。这会令空间翻倍、判胜逻辑也变复杂。±1 编码下的单一计数器已经天然区分了两个玩家正和为 1、负和为 2是最优形态# Inefficient approach self.rows_p1 [0] * n self.rows_p2 [0] * n # Optimal approach - single counter with 1/-1 self.rows [0] * n currentPlayer 1 if player 1 else -1 self.rows[row] currentPlayer两种方案的对比与选型维度方案一棋盘聚焦检查方案二±1 累计计数move 时间复杂度O(n)O(1)空间复杂度O(n²)O(n)存储内容完整棋盘仅 2n 2 个计数器是否能回显/回溯棋面能棋盘完整落盘不能未存具体落子实现难度低四个检查函数各自独立略低但需注意 ±1 编码与两条对角线判定若题目只要求判胜、不要求还原棋面LeetCode 348 正是如此方案二是工程上的优选每次操作恒定开销且不随棋盘增大而增长。方案一的价值在于可读性与可观测性——四个独立的 check 函数便于单元测试与棋面可视化。仓库中的相近思路1275 题的计数判胜本仓库在 1275-find-winner-on-a-tic-tac-toe-game.java 中还收录了「1275. Find Winner on a Tic Tac Toe Game」的解法它处理的是 3×3 固定棋盘、输入为落子序列moves的变体。从源码结构看该解法采用的正是方案二同一套计数思想用三维计数数组result[player][0/1][row/col]与两组对角线计数diag1、diag2每手落子后递增对应计数计数达到 3 即返回胜者区别仅在于此题棋盘固定为 3×3于是「达到 n」这一判定被具体化成了「达到 3」且反对角线被枚举为(0,2)、(1,1)、(2,0)三个坐标。对照两份代码可以看出「按行/列/对角线累计计数 阈值判定」是井字棋类题目的通用骨架n 只是阈值参数。小结判胜不必全盘扫描一次落子只可能通过其所在的行、列、至多两条对角线形成连线聚焦检查即可把暴力 O(n²) 降到 O(n)±1 累计编码把状态从「棋盘」压缩为「2n2 个计数器」让每次 move 的判胜开销恒定 O(1)空间降至 O(n)实现时盯紧三点反对角线条件是col n - row - 1、奇数棋盘中心格要同时更新两条对角线、两个玩家共用一套 ±1 计数器。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考