LeetCode 题解工作台
找出井字棋的获胜者
井字棋 是由两个玩家 A 和 B 在 3 x 3 的棋盘上进行的游戏。井字棋游戏的规则如下： 玩家轮流将棋子放在空方格 ( ' ' ) 上。 第一个玩家 A 总是用 'X' 作为棋子，而第二个玩家 B 总是用 'O' 作为棋子。 'X' 和 'O' 只能放在空方格中，而不能放在已经被占用的方格上。 …
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
由于 `moves` 都有效，也即是说，不存在某个人获胜后，其他人仍然落棋的情况。因此，只需判断最后一个落棋的人能否获胜即可。 我们用一个长度为 的数组 `cnt` 记录行、列以及对角线的落棋次数。其中 $cnt[0, 1, 2]$ 分别表示第 $0, 1, 2$ 行的落棋次数，而 $cnt[3, 4, 5]$ 分别表示第 $0, 1, 2$ 列的落棋次数，另外 和 分别表示两条对角线的落棋…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
井字棋 是由两个玩家 A 和 B 在 3 x 3 的棋盘上进行的游戏。井字棋游戏的规则如下：
- 玩家轮流将棋子放在空方格 (
' ') 上。 - 第一个玩家
A总是用'X'作为棋子，而第二个玩家B总是用'O'作为棋子。 'X'和'O'只能放在空方格中，而不能放在已经被占用的方格上。- 只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
- 如果所有方块都放满棋子（不为空），游戏也会结束。
- 游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中 moves[i] = [rowi, coli] 表示第 i 次移动在 grid[rowi][coli]。如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
你可以假设 moves 都 有效（遵循 井字棋 规则），网格最初是空的，A 将先行动。
示例 1：
输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 输出："A" 解释："A" 获胜，他总是先走。
示例 2：
输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] 输出："B" 解释："B" 获胜。
示例 3：
输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] 输出："Draw" 解释：由于没有办法再行动，游戏以平局结束。
提示：
1 <= moves.length <= 9moves[i].length == 20 <= moves[i][j] <= 2moves里没有重复的元素。moves遵循井字棋的规则。
解题思路
方法一：判断最后一个落棋的人能否获胜
由于 moves 都有效，也即是说，不存在某个人获胜后，其他人仍然落棋的情况。因此，只需判断最后一个落棋的人能否获胜即可。
我们用一个长度为 的数组 cnt 记录行、列以及对角线的落棋次数。其中 分别表示第 行的落棋次数，而 分别表示第 列的落棋次数，另外 和 分别表示两条对角线的落棋次数。落棋过程中，如果某个人在某一行、列或对角线上落棋次数达到 次，则该人获胜。
如果最后一个落棋的人没有获胜，那么我们判断棋盘是否已满，如果已满，则平局；否则，游戏尚未结束。
时间复杂度 ，空间复杂度 。其中 为 moves 的长度。
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
n = len(moves)
cnt = [0] * 8
for k in range(n - 1, -1, -2):
i, j = moves[k]
cnt[i] += 1
cnt[j + 3] += 1
if i == j:
cnt[6] += 1
if i + j == 2:
cnt[7] += 1
if any(v == 3 for v in cnt):
return "B" if k & 1 else "A"
return "Draw" if n == 9 else "Pending"
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) where n is the number of moves, since each move updates at most five counters. Space complexity is O(1) with fixed-size arrays or hash tables for rows, columns, and diagonals, independent of the number of moves. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting recognition of array scanning combined with hash lookup pattern.
- question_mark
May probe edge cases like immediate diagonal or row wins.
- question_mark
Check whether candidate handles 'Pending' vs 'Draw' correctly.
常见陷阱
外企场景- error
Failing to track diagonals separately, causing missed wins.
- error
Swapping players incorrectly and assigning moves to the wrong hash table.
- error
Checking the winner only at the end instead of after each move, missing early wins.
进阶变体
外企场景- arrow_right_alt
Larger grids such as NxN Tic Tac Toe, requiring scalable row, column, and diagonal tracking.
- arrow_right_alt
Tracking multiple simultaneous games in parallel, using hash tables per board.
- arrow_right_alt
Modifying the game rules to win with k consecutive marks instead of three.