doocs/leetcode 面试题 16.04「井字游戏」：用单次扫描计数法判定棋盘胜负、平局与未完-北京尧图网络

示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇基于 doocs/leetcode 仓库中 lcci/16.04.Tic-Tac-Toe/README.md 题解文档展开讲解《程序员面试金典》面试题 16.04Tic-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且第二个玩家总是放字符XX和O只允许放置在空位中不允许对已放有字符的位置进行填充当有 N 个相同且非空的字符填充任何行、列或对角线时游戏结束对应该字符的玩家获胜当所有位置非空时也算为游戏结束如果游戏结束玩家不允许再放置字符。算法的输出有三种可能语义必须严格区分返回值含义X或O存在获胜者返回获胜玩家使用的字符Draw没有玩家获胜且棋盘已无空位平局Pending没有玩家获胜但仍存在空位游戏未结束示例走读示例 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 记 1O 记 -1直接枚举所有行、列、两条对角线再逐个数子做法正确但与「边走边判定」存在重复统计。更紧凑的思路是把两种棋子映射为带符号的数值格子是X计数贡献1格子是O计数贡献-1格子是不贡献计 0。这样「某一行/列/对角线被同一方占满」这一条件就被转化为一个纯数值条件该方向的累计计数绝对值等于 N。若为N说明该方向全为X若为-N说明该方向全为O。由于合法局面至多一方获胜绝对值一旦达到 N当前扫描格子的字符就是获胜者。数据结构与判定流程整个算法只需要一次双重循环扫描README.md 中「方法一计数」的原文描述与此一致用一个长度为 N 的一维数组rows和一个长度 N 的数组cols分别累计每一行、每一列的带符号计数用两个标量dg主对角线i j和udg副对角线i j 1 n即i j n - 1累计两条对角线的计数用一个布尔变量hasEmptyGrid记录是否出现过空位扫描到格子(i, j)时根据字符是X还是O更新rows[i]、cols[j]以及若在对应对角线上dg、udg每次更新后检查abs(rows[i]) n || abs(cols[j]) n || abs(dg) n || abs(udg) n一旦成立立即返回该格字符扫描结束仍未命中任何获胜条件则根据hasEmptyGrid返回Pending仍有空位或Draw已填满。判定优先级由此自然形成获胜平局未完——获胜是在扫描途中「短路返回」只有完全没扫出任何获胜线才会走到最后的Draw/Pending二选一。以示例 1N 3演示计数过程格子 (i, j)字符vrows[i]cols[j]dgudg是否命中(0,0)O-1-1-1-10否(0,1)0-10-10否记 hasEmptyGrid(0,2)X10-1-11否(1,0)00-1-11否(1,1)X11002否(1,2)O-10-101否(2,0)X11101否(2,1)01101否(2,2)O-100-10否等等——示例 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/ 目录下提供了六种语言的独立实现文件核心逻辑完全同构下面逐一给出。Python3Solution.pyclass 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 DrawPython 版有一个与其他语言不同的写法细节它对空格先算出v -1再将其改写为0即空位也会执行一次「加 0」的更新由于 N 1abs(0) n恒不成立因此不会误触发获胜判定行为与「跳过空格」完全等价。JavaSolution.javaclass 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把「记录空位」和「累加计数」两条路径显式分开逻辑分支更直白。GoSolution.gofunc 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 ij 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 版有两点值得注意一是副对角线条件写作ij n-1与 C/Java 的i j 1 n完全等价二是 LeetCode Go 题解环境没有可直接使用的整数abs因此附带了一个手写的abs辅助函数这在移植该代码到其他 Go 项目时不能遗漏。CSolution.cppclass Solution { public: string tictactoe(vectorstring board) { int n board.size(); vectorint 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的显式转换避免了依赖隐式转换的写法差异。TypeScriptSolution.tsfunction 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; }SwiftSolution.swiftclass 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 nJava、C、Python和i j n - 1Go、TypeScript、Swift两种写法二者数学等价。主对角线条件则统一为i j。写错任一条件都会漏判某条对角线上的三连N 连这是移植该解法时最容易踩的坑。N 1 的退化情形。约束允许 N 从 1 开始。此时棋盘只有一个格子主对角线与副对角线重合于 (0,0)若该格是Odg与udg同时变为 -1abs(-1) 1 n命中返回O——这也符合规则先手 O 落子即占满唯一的行/列/对角线若该格是空格则hasEmptyGrid为真返回Pending。为何可以「发现即返回」。题目保证「输入一定遵循井字棋规则」即 O 先手、双方严格交替、不允许覆盖。在这样的合法局面下若 X 已连成 N 子则 O 的落子数至多等于 XO 不可能同时先一步连成 N 子。因此扫描途中返回第一个获胜者不会漏掉任何「双方同时获胜」的情况如果输入不合法如出现双胜本算法会返回扫描顺序中先被发现的一方这是题目约束之外的行为不必处理。空格的两种处理等价。Python 版把空格映射为v 0后继续走更新与判定流程其余语言在空格处continue。由于约束中n 1abs(0) n永远为假两条路径在判定结果上完全一致只是代码组织风格不同。复杂度边界。N 上限为 100O(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.pyPython3 实现lcci/16.04.Tic-Tac-Toe/Solution.javaJava 实现lcci/16.04.Tic-Tac-Toe/Solution.goGo 实现含手写abslcci/16.04.Tic-Tac-Toe/Solution.cppC 实现lcci/16.04.Tic-Tac-Toe/Solution.tsTypeScript 实现lcci/16.04.Tic-Tac-Toe/Solution.swiftSwift 实现lcci/lcci.json本题frontend_id 为「面试题 16.04」的题目标题、难度Medium/中等与标签Array/数组等元数据。掌握「带符号计数绝对值达标即短路」这一模式后可以把它推广到所有「N 子连线判定」类问题如更大棋盘的 Gomoku 行/列/对角线状态维护只要胜负条件能表达为「某方向上单一玩家的连续占位达到阈值」都适合用方向累加器代替逐线枚举。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐0348. 设计井字棋LeetCode 设计类用计数法把 n×n 棋盘每次落子的胜负判定优化到 O(1)0348. 设计井字棋LeetCode 设计类用计数法把 n×n 棋盘每次落子的胜负判定优化到 O 1 本文是「算法通关手册」AlgoNote对 Le教程文档知识库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 镜像的操作系统固件开发工具上一篇PinchTab Agent CLI 测试蓝图深度解析Setup/Server/Config 命令的 Agent 友好性验证下一篇openFrameworks iOS 实战用 ofxAssimpModelLoader 在 iPhone/iPad 上加载与播放 3D 动画模型assimpExample 深度解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

doocs/leetcode 面试题 16.04「井字游戏」：用单次扫描计数法判定棋盘胜负、平局与未完

相关推荐

C/C++数据范围全解析：整型溢出、浮点精度与跨平台陷阱

DirectX 11键鼠输入处理：Win32消息机制与渲染循环协作实战

社交媒体海量行为数据如何用Hadoop体系完成存储、治理与离线计算

更多资讯

手动部署OpenTelemetry Collector：从配置到运维的实践指南

SpringBoot整合knife4j实战：接口文档与在线调试完整指南

二次规划QP实战：从调包到手撕，解决不可行与病态问题

差分进化算法MATLAB源码详解：用Sphere函数跑通单目标优化

Dubbo整合Spring服务注册与暴露机制深度解析

Docker Compose 容器化部署 ChirpStack LoRaWAN 网络服务器实战

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？