LeetCode 1275. Find Winner on a Tic Tac Toe Game：井字棋胜负判定的 Go 模拟解法

LeetCode 1275. Find Winner on a Tic Tac Toe Game：井字棋胜负判定的 Go 模拟解法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 1275. Find Winner on a Tic Tac Toe Game 题目文档 为核心，完整讲解井字棋（Tic-Tac-Toe）游戏的胜负判定问题：如何在给定落子序列后输出"A"、"B"、"Draw"或"Pending"。读完本文，你将掌握基于棋盘模拟的行、列、对角线直线判定方法，并能对照仓库源码与测试用例验证实现正确性。

题目概述

两位玩家 A 和 B 在一个 3 × 3 的网格上玩井字棋，游戏规则如下：

• 玩家轮流将棋子放入空方格（" "）中；
• 第一个玩家 A 始终使用"X"棋子，第二个玩家 B 始终使用"O"棋子；
• "X"和"O"只能放入空方格，不能覆盖已占用的方格；
• 当任意行、列或对角线上出现 3 个相同的（非空）棋子时，游戏结束；
• 当所有方格都被占满（非空）时，游戏同样结束；
• 游戏结束后不能再落子。

给定一个数组moves，其中每个元素是大小为 2 的数组，对应网格的行（row）和列（column），元素按 A 和 B 轮流落子的顺序记录各自棋子的位置。要求返回：

• 存在获胜者时返回"A"或"B"；
• 游戏以平局结束（9 格全部占满且无人获胜）时返回"Draw"；
• 游戏尚未结束、仍有可行动作时返回"Pending"。

可以假设moves是有效的（遵循井字棋规则），网格初始为空，且A 先手。完整题目描述见 原题文档。

输入输出示例

示例 1：A 获胜

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: "A" Explanation: "A" wins, he always plays first. "X " "X " "X " "X " "X " " " -> " " -> " X " -> " X " -> " X " " " "O " "O " "OO " "OOX"

A 的最后一步落在(2,2)，此时第三行"OOX"中X连成一线，A 获胜。

示例 2：B 获胜

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] Output: "B" Explanation: "B" wins. "X " "X " "XX " "XXO" "XXO" "XXO" " " -> " O " -> " O " -> " O " -> "XO " -> "XO " " " " " " " " " " " "O "

B 的第 3 步落在(2,0)，第三列"X"、"X"、"O"中O连成一线，B 获胜。

示例 3：平局

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] Output: "Draw" Explanation: The game ends in a draw since there are no moves to make. "XXO" "OOX" "XOX"

9 个方格全部落满且没有任何一方连成一线，判定为平局。

示例 4：游戏未结束

Input: moves = [[0,0],[1,1]] Output: "Pending" Explanation: The game has not finished yet. "X " " O " " "

仅落子 2 步，棋盘远未填满且无人获胜，返回"Pending"。

约束条件

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= moves[i][j] <= 2
• moves中没有重复元素
• moves遵循井字棋规则（即不会出现已占位、超时落子等非法状态）

这些约束保证了棋盘坐标始终合法、落子序列不会冲突，且总步数不会超过 9 步，因此算法无需处理任何非法输入分支。

解题思路

这是 LeetCode 简单难度题，核心策略是模拟 + 直线判定：

1. 模拟落子：由于赢得比赛至少需要 3 步，而moves数组最多 9 步，可以直接按照给定的步数顺序，把 A 和 B 的棋子放到棋盘上。由于 A 先手，所以偶数下标（i % 2 == 0）的步属于 A（放置'X'），奇数下标的步属于 B（放置'O'）。
2. 判定胜负：依次检查三行、三列，以及主对角线（(0,0)-(1,1)-(2,2)）和副对角线（(0,2)-(1,1)-(2,0)）共 8 条线，只要某条线被'X'填满就返回"A"，被'O'填满就返回"B"。
3. 收尾判定：如果 8 条线都没有人获胜，说明不是平局就是死局（Pending）。此时若len(moves) < 9，说明棋盘还有空位、仍有行动可走，返回"Pending"；否则 9 格已满且无人获胜，返回"Draw"。

由于题目保证moves有效，判定到某方胜利时该方必然已经走满了 3 步，因此不需要额外校验步数。

Go 源码实现

仓库中的实现位于 1275. Find Winner on a Tic Tac Toe Game.go，与题目文档中给出的代码完全一致：

func tictactoe(moves [][]int) string { board := [3][3]byte{} for i := 0; i < len(moves); i++ { if i%2 == 0 { board[moves[i][0]][moves[i][1]] = 'X' } else { board[moves[i][0]][moves[i][1]] = 'O' } } for i := 0; i < 3; i++ { if board[i][0] == 'X' && board[i][1] == 'X' && board[i][2] == 'X' { return "A" } if board[i][0] == 'O' && board[i][1] == 'O' && board[i][2] == 'O' { return "B" } if board[0][i] == 'X' && board[1][i] == 'X' && board[2][i] == 'X' { return "A" } if board[0][i] == 'O' && board[1][i] == 'O' && board[2][i] == 'O' { return "B" } } if board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X' { return "A" } if board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O' { return "B" } if board[0][2] == 'X' && board[1][1] == 'X' && board[2][0] == 'X' { return "A" } if board[0][2] == 'O' && board[1][1] == 'O' && board[2][0] == 'O' { return "B" } if len(moves) < 9 { return "Pending" } return "Draw" }

实现细节剖析

• 棋盘数据结构：board := [3][3]byte{}使用固定大小的二维字节数组，天然贴合 3 × 3 棋盘，无需动态扩容；用'X'/'O'标记落子，空位保持零值0。
• 先手归属：i%2 == 0对应 A（偶数步），i%2 == 1对应 B（奇数步），与"A 总是先手"的规则一一对应。
• 行、列判定合并循环：外层for i := 0; i < 3; i++一次循环内同时检查第i行（board[i][0]、board[i][1]、board[i][2]）和第i列（board[0][i]、board[1][i]、board[2][i]），用一次遍历覆盖全部 6 条行/列直线。
• 对角线单独判定：主对角线(0,0)-(1,1)-(2,2)与副对角线(0,2)-(1,1)-(2,0)无法用单一下标统一表达，故在循环后分别判断，共 4 个 if 分支。
• 判定顺序决定结果优先级：胜负判定在Pending/Draw之前完成，确保"先胜后平、先胜后未完成"的语义正确；例如 moves 长度为 5 且 A 已经连成一线时，会优先返回"A"而不是"Pending"。

测试用例验证

仓库配套的单测位于 1275. Find Winner on a Tic Tac Toe Game_test.go，Test_Problem1275采用表驱动（table-driven）测试风格：用question1275结构体组合输入参数para1275{one [][]int}与期望输出ans1275{one string}，依次对每组样例调用tictactoe并断言结果，失败时通过t.Fatalf输出输入与期望差异。

测试覆盖了如下典型场景：

可以看出，测试不仅覆盖了题目的 4 个官方示例，还补充了行、列、主对角线、副对角线各自独立的胜负分支，确保 8 条直线的判定逻辑全部被验证到。从测试结构看，该仓库延续了"每题一个测试文件、表驱动全场景覆盖"的组织风格，题目文档、实现源码与测试三者相互印证。

复杂度分析

• 时间复杂度：模拟落子阶段为O(m)，其中m = len(moves)（1 <= m <= 9）；胜负判定阶段为常数次比较（3 次循环 + 4 次对角线判断），整体时间复杂度为O(1)量级。
• 空间复杂度：仅使用一个 3 × 3 的board数组，空间复杂度为O(1)。

由于棋盘规模固定为 3 × 3，无论输入步数多少，算法的时空开销都被严格限制在常数范围内，这也是该解法无需任何剪枝或优化即可通过全部测试的原因。

边界情况与扩展思考

1. 最短获胜步数：A 最快在第 5 步（第 3 次落子）获胜，B 最快在第 6 步获胜；若moves长度不足 5，可直接断定结果为"Pending"（本解法通过通用判定路径自动覆盖）。
2. 先手优势：因为 A 先手且题设保证moves有效，不可能出现 B 已经获胜但 A 又继续落子的非法序列，因此无需在判定后校验"游戏是否应提前结束"。
3. 判定与步数的耦合：胜负判定先于len(moves) < 9判断是本题的关键顺序，若颠倒顺序，会把"已分胜负但棋盘未满"的输入误判为"Pending"。
4. 扩展场景：若棋盘规模变为 N × N，可将行/列判定改为计数统计（记录每行、每列、两条对角线上的棋子数），并在每次落子后增量更新，从而在O(1)内完成单步胜负检查，这是本题思路在更大棋盘上的自然延伸。

小结

LeetCode 1275 是一道典型的"小棋盘模拟"题：固定 3 × 3 规模让暴力枚举 8 条直线成为最简单可靠的方案。本仓库的实现以[3][3]byte棋盘模拟落子、按行/列/对角线顺序判定胜负、以步数兜底区分"Pending"与"Draw"，逻辑清晰且测试完备。读者可直接阅读 题目文档、实现源码 与 测试用例 对照学习，也可以沿袭"模拟 + 直线判定"的思路处理更大规模的棋盘变体。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go