• 示例工程
• 教程

本篇基于 doocs/leetcode 仓库中 lcci/16.04.Tic-Tac-Toe/README.md 题解文档展开，讲解《程序员面试金典》面试题 16.04（Tic-Tac-Toe）的完整解法：如何对 N x N 井字棋盘做一次 O(n²) 扫描，通过「行/列/对角线带符号计数」同时判定获胜者（X或O）、平局（Draw）与未完（Pending）三种终态，并对照仓库中 Python、Java、Go、C++、TypeScript、Swift 六种语言的实现剖析其细节与边界情况。

题目描述：从 N x N 棋盘判定游戏状态

规则与输出语义

设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "（空位）、"X"和"O"组成。井字游戏的规则如下：

• 玩家轮流将字符放入空位（" "）中；
• 第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"；
• "X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充；
• 当有 N 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜；
• 当所有位置非空时，也算为游戏结束；
• 如果游戏结束，玩家不允许再放置字符。

算法的输出有三种可能，语义必须严格区分：

示例走读

示例 1：

输入：board = ["O X"," XO","X O"] 输出："X"

棋盘为：

O . X . X O X . O

三条主对角线上的X连成 N 个相同字符，X 获胜。注意第 3 行的X . O并不构成 O 的三连（第 3 列是X O O），判定必须精确到「同一行、同一列或同一条对角线上恰好 N 个相同非空字符」。

示例 2：

输入：board = ["OOX","XXO","OXO"] 输出："Draw" 解释：没有玩家获胜且不存在空位

9 个格子全部填满但没有任何一条行/列/对角线连成，属于平局。

示例 3：

输入：board = ["OOX","XXO","OX "] 输出："Pending" 解释：没有玩家获胜且仍存在空位

与示例 2 的唯一区别是右下角仍为空位，因此返回"Pending"。

输入约束

• 1 <= board.length == board[i].length <= 100（棋盘是边长不超过 100 的正方形）；
• 输入一定遵循井字棋规则。

第二条约束很关键：它保证了棋盘状态是「O 先手、双方交替落子、不覆盖已有字符」合法演化出来的。由此可以推断：合法局面下至多只有一方获胜（不可能出现 X 和 O 同时各自连成 N 子），所以扫描过程中一旦发现任意一条获胜线，立即返回当前格子的字符就是安全的，无需继续检查是否存在另一方的获胜线。

解法设计：单次扫描的带符号计数

核心思想：X 记 +1，O 记 -1

直接枚举所有行、列、两条对角线再逐个数子，做法正确但与「边走边判定」存在重复统计。更紧凑的思路是把两种棋子映射为带符号的数值：

• 格子是X：计数贡献+1；
• 格子是O：计数贡献-1；
• 格子是" "：不贡献（计 0）。

这样「某一行/列/对角线被同一方占满」这一条件，就被转化为一个纯数值条件：该方向的累计计数绝对值等于 N。若为+N说明该方向全为X，若为-N说明该方向全为O。由于合法局面至多一方获胜，绝对值一旦达到 N，当前扫描格子的字符就是获胜者。

数据结构与判定流程

整个算法只需要一次双重循环扫描（README.md 中「方法一：计数」的原文描述与此一致）：

1. 用一个长度为 N 的一维数组rows和一个长度 N 的数组cols分别累计每一行、每一列的带符号计数；
2. 用两个标量dg（主对角线，i == j）和udg（副对角线，i + j + 1 == n，即i + j == n - 1）累计两条对角线的计数；
3. 用一个布尔变量hasEmptyGrid记录是否出现过空位；
4. 扫描到格子(i, j)时，根据字符是X还是O更新rows[i]、cols[j]以及（若在对应对角线上）dg、udg；每次更新后检查abs(rows[i]) == n || abs(cols[j]) == n || abs(dg) == n || abs(udg) == n，一旦成立立即返回该格字符；
5. 扫描结束仍未命中任何获胜条件，则根据hasEmptyGrid返回Pending（仍有空位）或Draw（已填满）。

判定优先级由此自然形成：获胜 > 平局 > 未完——获胜是在扫描途中「短路返回」，只有完全没扫出任何获胜线，才会走到最后的Draw/Pending二选一。

以示例 1（N = 3）演示计数过程：

等等——示例 1 的返回是"X"，但按上表主对角线dg只累计了 O、X、O 三个格子，绝对值到不了 3。重新检查：该棋盘主对角线为 (0,0)=O、(1,1)=X、(2,2)=O，副对角线为 (0,2)=X、(1,1)=X、(2,0)=X。X 的三连在副对角线udg上：udg 累计为 +1（(0,2)）+1（(1,1)）+1（(2,0)）= 3，在扫到 (2,0) 时abs(udg) == 3 == n，返回该格字符X。这也说明两条对角线都要在每次更新后参与判定，缺一不可。

复杂度

• 时间复杂度 O(n²)：每个格子只访问一次，每次只做 O(1) 的更新与判断；
• 空间复杂度 O(n)：仅用于存放rows与cols两个长度为 N 的计数数组，dg、udg、hasEmptyGrid为 O(1)。

多语言实现

仓库在 lcci/16.04.Tic-Tac-Toe/ 目录下提供了六种语言的独立实现文件，核心逻辑完全同构，下面逐一给出。

Python3（Solution.py）

class Solution: def tictactoe(self, board: List[str]) -> str: n = len(board) rows = [0] * n cols = [0] * n dg = udg = 0 has_empty_grid = False for i, row in enumerate(board): for j, c in enumerate(row): v = 1 if c == 'X' else -1 if c == ' ': has_empty_grid = True v = 0 rows[i] += v cols[j] += v if i == j: dg += v if i + j + 1 == n: udg += v if ( abs(rows[i]) == n or abs(cols[j]) == n or abs(dg) == n or abs(udg) == n ): return c return 'Pending' if has_empty_grid else 'Draw'

Python 版有一个与其他语言不同的写法细节：它对空格先算出v = -1再将其改写为0，即空位也会执行一次「加 0」的更新；由于 N >= 1，abs(0) == n恒不成立，因此不会误触发获胜判定，行为与「跳过空格」完全等价。

Java（Solution.java）

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"; } }

Java/C++ 版对空格直接continue，把「记录空位」和「累加计数」两条路径显式分开，逻辑分支更直白。

Go（Solution.go）

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 }

Go 版有两点值得注意：一是副对角线条件写作i+j == n-1，与 C++/Java 的i + j + 1 == n完全等价；二是 LeetCode Go 题解环境没有可直接使用的整数abs，因此附带了一个手写的abs辅助函数，这在移植该代码到其他 Go 项目时不能遗漏。

C++（Solution.cpp）

class Solution { public: string tictactoe(vector<string>& board) { int n = board.size(); vector<int> rows(n), cols(n); int dg = 0, udg = 0; bool hasEmptyGrid = false; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { char c = board[i][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 (abs(rows[i]) == n || abs(cols[j]) == n || abs(dg) == n || abs(udg) == n) { return string(1, c); } } } return hasEmptyGrid ? "Pending" : "Draw"; } };

C++ 版返回单个字符时使用string(1, c)构造单字符字符串，这是从char到string的显式转换，避免了依赖隐式转换的写法差异。

TypeScript（Solution.ts）

function tictactoe(board: string[]): string { const n = board.length; const rows = Array(n).fill(0); const cols = Array(n).fill(0); let [dg, udg] = [0, 0]; let hasEmptyGrid = false; for (let i = 0; i < n; ++i) { for (let j = 0; j < n; ++j) { const c = board[i][j]; if (c === ' ') { hasEmptyGrid = true; continue; } const v = c === 'X' ? 1 : -1; rows[i] += v; cols[j] += v; if (i === j) { dg += v; } if (i + j === n - 1) { udg += v; } if ( Math.abs(rows[i]) === n || Math.abs(cols[j]) === n || Math.abs(dg) === n || Math.abs(udg) === n ) { return c; } } } return hasEmptyGrid ? 'Pending' : 'Draw'; }

Swift（Solution.swift）

class Solution { func tictactoe(_ board: [String]) -> String { let n = board.count var rows = Array(repeating: 0, count: n) var cols = Array(repeating: 0, count: n) var diagonal = 0, antiDiagonal = 0 var hasEmptyGrid = false for i in 0..<n { for j in 0..<n { let c = Array(board[i])[j] if c == " " { hasEmptyGrid = true continue } let value = c == "X" ? 1 : -1 rows[i] += value cols[j] += value if i == j { diagonal += value } if i + j == n - 1 { antiDiagonal += value } if abs(rows[i]) == n || abs(cols[j]) == n || abs(diagonal) == n || abs(antiDiagonal) == n { return String(c) } } } return hasEmptyGrid ? "Pending" : "Draw" } }

Swift 版将变量命名为diagonal/antiDiagonal，语义更清晰；由于 Swift 中字符串不是可按下标直接取字符的定长序列，这里用Array(board[i])[j]把行转为字符数组后取第j个字符。

实现细节与边界情况

为什么用绝对值而不是分别计数。如果为 X、O 各维护一套行/列/对角线计数，需要 4 组长度为 N 的数组加 4 个标量，且判定逻辑翻倍。带符号计数把「两方竞争」压缩进一个数值轴：绝对值达到 N 时，符号本身（正为 X、负为 O）已经隐含了获胜者是谁，因此返回值直接取当前扫描格c即可——命中时该格子必然是刚补全这条线的那个棋子。

副对角线条件的两种等价写法。仓库实现中同时出现了i + j + 1 == n（Java、C++、Python）和i + j == n - 1（Go、TypeScript、Swift）两种写法，二者数学等价。主对角线条件则统一为i == j。写错任一条件都会漏判某条对角线上的三连（N 连），这是移植该解法时最容易踩的坑。

N = 1 的退化情形。约束允许 N 从 1 开始。此时棋盘只有一个格子，主对角线与副对角线重合于 (0,0)：若该格是O，dg与udg同时变为 -1，abs(-1) == 1 == n命中，返回"O"——这也符合规则（先手 O 落子即占满唯一的行/列/对角线）；若该格是空格，则hasEmptyGrid为真，返回"Pending"。

为何可以「发现即返回」。题目保证「输入一定遵循井字棋规则」，即 O 先手、双方严格交替、不允许覆盖。在这样的合法局面下，若 X 已连成 N 子，则 O 的落子数至多等于 X，O 不可能同时先一步连成 N 子。因此扫描途中返回第一个获胜者不会漏掉任何「双方同时获胜」的情况；如果输入不合法（如出现双胜），本算法会返回扫描顺序中先被发现的一方，这是题目约束之外的行为，不必处理。

空格的两种处理等价。Python 版把空格映射为v = 0后继续走更新与判定流程；其余语言在空格处continue。由于约束中n >= 1，abs(0) == n永远为假，两条路径在判定结果上完全一致，只是代码组织风格不同。

复杂度边界。N 上限为 100，O(n²) 扫描最多 10000 次格子访问、O(n) 即至多 200 个整型计数槽，在任意语言下都是常数级的轻量开销，无需为「大棋盘」做额外优化。

仓库文件索引

围绕本题在 doocs/leetcode 仓库中的全部资料：

• lcci/16.04.Tic-Tac-Toe/README.md：中文题解（本题目描述、规则、示例与计数解法原文）；
• lcci/16.04.Tic-Tac-Toe/README_EN.md：英文版题解；
• lcci/16.04.Tic-Tac-Toe/Solution.py：Python3 实现；
• lcci/16.04.Tic-Tac-Toe/Solution.java：Java 实现；
• lcci/16.04.Tic-Tac-Toe/Solution.go：Go 实现（含手写abs）；
• lcci/16.04.Tic-Tac-Toe/Solution.cpp：C++ 实现；
• lcci/16.04.Tic-Tac-Toe/Solution.ts：TypeScript 实现；
• lcci/16.04.Tic-Tac-Toe/Solution.swift：Swift 实现；
• lcci/lcci.json：本题（frontend_id 为「面试题 16.04」）的题目标题、难度（Medium/中等）与标签（Array/数组）等元数据。

掌握「带符号计数 + 绝对值达标即短路」这一模式后，可以把它推广到所有「N 子连线判定」类问题（如更大棋盘的 Gomoku 行/列/对角线状态维护）：只要胜负条件能表达为「某方向上单一玩家的连续占位达到阈值」，都适合用方向累加器代替逐线枚举。

• 示例工程
• 教程