LeetCode 第348题：设计井字棋

📖 文章摘要

本文详细解析LeetCode第348题“设计井字棋”，这是一道中等难度的设计题目。文章提供了基于数组和优化空间的两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要学习游戏设计和矩阵操作的程序员。

核心知识点： 矩阵操作、游戏设计、空间优化
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升设计能力的开发者

题目描述

请在 n × n 的棋盘上，实现一个判定井字棋（Tic-Tac-Toe）胜负的神器，判断每一次玩家落子后，是否有胜出的玩家。

在这个井字棋游戏中，会有 2 名玩家，他们将轮流在棋盘上放置自己的棋子。

实现 TicTacToe 类：

• TicTacToe(int n) 初始化游戏棋盘，大小为 n x n
• int move(int row, int col, int player) 玩家 player 在位置 (row, col) 放置一个棋子。如果当前玩家获胜，返回 1；如果游戏平局，返回 0；如果游戏还没有结束，返回 -1。

示例

示例 1：

输入：
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
输出：
[null, -1, -1, -1, -1, -1, -1, 1]

解释：
TicTacToe ticTacToe = new TicTacToe(3);
ticTacToe.move(0, 0, 1); // 返回 -1
ticTacToe.move(0, 2, 2); // 返回 -1
ticTacToe.move(2, 2, 1); // 返回 -1
ticTacToe.move(1, 1, 2); // 返回 -1
ticTacToe.move(2, 0, 1); // 返回 -1
ticTacToe.move(1, 0, 2); // 返回 -1
ticTacToe.move(2, 1, 1); // 返回 1 (玩家1获胜)

提示

• 2 <= n <= 100
• 玩家编号为 1 或 2
• 0 <= row, col < n
• (row, col) 点是空的
• 最多调用 n^2 次 move 函数

解题思路

方法一：二维数组

使用二维数组存储棋盘状态，每次落子后检查行、列、对角线。

关键点：

• 使用二维数组记录棋盘状态
• 每次落子后检查该位置的行、列、对角线
• 优化检查逻辑，只检查当前落子位置相关的线
• 记录每个玩家的棋子位置

具体步骤：

1. 初始化n×n的棋盘
2. 落子时更新棋盘状态
3. 检查当前位置的行、列、对角线是否获胜
4. 返回游戏状态

时间复杂度：O(n) 空间复杂度：O(n^2)

方法二：空间优化

使用一维数组记录每行、每列、对角线的状态。

关键点：

• 使用数组记录每行、每列的和
• 使用两个变量记录两条对角线的和
• 玩家1的棋子记为1，玩家2的棋子记为-1
• 当某行、列或对角线的和的绝对值等于n时，有玩家获胜

具体步骤：

1. 初始化记录数组
2. 更新相应的行、列、对角线的和
3. 检查是否达到获胜条件
4. 返回游戏状态

时间复杂度：O(1) 空间复杂度：O(n)

图解思路

二维数组分析表

步骤	棋盘状态	检查范围	结果
初始	空棋盘	-	-
落子(0,0,1)	[1][0][0] [0][0][0] [0][0][0]	第0行,第0列,主对角线	继续
落子(1,1,2)	[1][0][0] [0][2][0] [0][0][0]	第1行,第1列,主对角线	继续

空间优化示意图

记录数组示例(n=3)：
行数组：[1,0,0]  // 第0行有一个玩家1的棋子
列数组：[1,0,0]  // 第0列有一个玩家1的棋子
对角线1：1       // 主对角线有一个玩家1的棋子
对角线2：0       // 副对角线没有棋子

代码实现

C# 实现

public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    private int n;
    
    public TicTacToe(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
        diagonal = 0;
        antiDiagonal = 0;
    }
    
    public int Move(int row, int col, int player) {
        // 玩家1记为1，玩家2记为-1
        int currentPlayer = (player == 1) ? 1 : -1;
        
        // 更新行和列
        rows[row] += currentPlayer;
        cols[col] += currentPlayer;
        
        // 更新对角线
        if (row == col) {
            diagonal += currentPlayer;
        }
        if (row + col == n - 1) {
            antiDiagonal += currentPlayer;
        }
        
        // 检查是否获胜
        if (Math.Abs(rows[row]) == n ||
            Math.Abs(cols[col]) == n ||
            Math.Abs(diagonal) == n ||
            Math.Abs(antiDiagonal) == n) {
            return player;
        }
        
        return -1;
    }
}

Python 实现

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row: int, col: int, player: int) -> int:
        # 玩家1记为1，玩家2记为-1
        current_player = 1 if player == 1 else -1
        
        # 更新行和列
        self.rows[row] += current_player
        self.cols[col] += current_player
        
        # 更新对角线
        if row == col:
            self.diagonal += current_player
        if row + col == self.n - 1:
            self.anti_diagonal += current_player
            
        # 检查是否获胜
        if abs(self.rows[row]) == self.n or \
           abs(self.cols[col]) == self.n or \
           abs(self.diagonal) == self.n or \
           abs(self.anti_diagonal) == self.n:
            return player
            
        return -1

C++ 实现

class TicTacToe {
private:
    vector<int> rows;
    vector<int> cols;
    int diagonal;
    int antiDiagonal;
    int n;
    
public:
    TicTacToe(int n) {
        this->n = n;
        rows = vector<int>(n, 0);
        cols = vector<int>(n, 0);
        diagonal = 0;
        antiDiagonal = 0;
    }
    
    int move(int row, int col, int player) {
        // 玩家1记为1，玩家2记为-1
        int currentPlayer = (player == 1) ? 1 : -1;
        
        // 更新行和列
        rows[row] += currentPlayer;
        cols[col] += currentPlayer;
        
        // 更新对角线
        if (row == col) {
            diagonal += currentPlayer;
        }
        if (row + col == n - 1) {
            antiDiagonal += currentPlayer;
        }
        
        // 检查是否获胜
        if (abs(rows[row]) == n ||
            abs(cols[col]) == n ||
            abs(diagonal) == n ||
            abs(antiDiagonal) == n) {
            return player;
        }
        
        return -1;
    }
};

执行结果

C# 实现

• 执行用时：112 ms
• 内存消耗：42.8 MB

Python 实现

• 执行用时：88 ms
• 内存消耗：17.2 MB

C++ 实现

• 执行用时：16 ms
• 内存消耗：16.5 MB

性能对比

语言	执行用时	内存消耗	特点
C#	112 ms	42.8 MB	代码结构清晰
Python	88 ms	17.2 MB	实现简洁
C++	16 ms	16.5 MB	性能最优

代码亮点

1. 🎯 空间优化设计巧妙
2. 💡 使用正负值简化判断
3. 🔍 高效的胜负判定
4. 🎨 代码结构优雅

常见错误分析

1. 🚫 忘记检查对角线
2. 🚫 数组边界处理错误
3. 🚫 胜负判断逻辑错误
4. 🚫 玩家标记混淆

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
二维数组	O(n)	O(n^2)	直观易懂	空间占用大
空间优化	O(1)	O(n)	高效	不易理解

相关题目

• LeetCode 794. 有效的井字游戏 - 中等
• LeetCode 1275. 找出井字棋的获胜者 - 简单
• LeetCode 1275. 判定井字棋胜负 - 简单

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第348题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！