当前位置：首页 > article >正文

LeetCode1275

article 2025/3/10 15:14:01

LeetCode1275

题目描述

给定一个 3x3 的井字棋棋盘，moves 数组表示玩家的落子顺序，其中 moves[i] = [row, col] 表示第 i 步落子的位置。玩家 A 先手，玩家 B 后手。你需要根据 moves 判断游戏的胜负情况。

返回值：

如果玩家 A 获胜，返回 "A"。
如果玩家 B 获胜，返回 "B"。
如果游戏未结束且没有玩家获胜，返回 "Pending"。
如果游戏结束且没有玩家获胜，返回 "Draw"。

示例

示例 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"

解释:

游戏结束，没有玩家获胜。

思路分析

问题核心

我们需要根据玩家的落子顺序，判断游戏的胜负情况。

思路拆解

检查最后一步：
- 检查最后一步落子的玩家是否形成了三连线。
统计落子情况：
- 统计最后一步落子的玩家在行、列、对角线上的落子数量。
判断胜负：
- 如果某个方向上的落子数量达到 3，则该玩家获胜。
判断游戏状态：
- 如果所有步数已满且没有玩家获胜，则返回 "Draw"。
- 如果步数未满且没有玩家获胜，则返回 "Pending"。

代码段

class Solution {
    public String tictactoe(int[][] moves) {
        int len = moves.length;
        int[] dp = moves[len - 1];
        int x = 0, y = 0, x_y = 0, y_x = 0;
        int count = len - 1;
        while (count >= 0) {
            int[] cur = moves[count];
            if (cur[1] == dp[1]) x++;
            if (cur[0] == dp[0]) y++;
            if (cur[0] == cur[1]) x_y++;
            if (cur[0] + cur[1] == 2) y_x++;
            count -= 2;
        }
        if (x >= 3 || y >= 3 || x_y >= 3 || y_x >= 3) {
            return len % 2 == 0 ? "B" : "A";
        }
        if (len < 9) return "Pending";
        return "Draw";
    }
}

在这里插入图片描述

代码逐行讲解

获取步数和最后一步：
```
int len = moves.length;
int[] dp = moves[len - 1];
```
- 获取步数 len 和最后一步的落子位置 dp。
初始化统计变量：
```
int x = 0, y = 0, x_y = 0, y_x = 0;
```
- x 统计列方向的落子数量。
- y 统计行方向的落子数量。
- x_y 统计主对角线方向的落子数量。
- y_x 统计副对角线方向的落子数量。

统计落子情况：

int count = len - 1;
while (count >= 0) {
    int[] cur = moves[count];
    if (cur[1] == dp[1]) x++;
    if (cur[0] == dp[0]) y++;
    if (cur[0] == cur[1]) x_y++;
    if (cur[0] + cur[1] == 2) y_x++;
    count -= 2;
}

从最后一步开始，每隔一步统计一次落子情况。

判断胜负：

if (x >= 3 || y >= 3 || x_y >= 3 || y_x >= 3) {
    return len % 2 == 0 ? "B" : "A";
}

如果某个方向上的落子数量达到 3，则返回获胜玩家。

判断游戏状态：
```
if (len < 9) return "Pending";
return "Draw";
```
- 如果步数未满且没有玩家获胜，则返回 "Pending"。
- 如果步数已满且没有玩家获胜，则返回 "Draw"。

复杂度分析

时间复杂度

遍历步数的时间复杂度为 O(n/2)，其中 n 是步数。
因此，总时间复杂度为 O(n)。

空间复杂度

只使用了常数级别的额外空间，因此空间复杂度为 O(1)。

总结的知识点

井字棋规则：
- 理解井字棋的胜负规则和三连线的判断方法。
遍历与统计：
- 通过遍历步数统计落子情况。
条件判断：
- 根据统计结果判断游戏的胜负和状态。

整合

class Solution {
    public String tictactoe(int[][] moves) {
        int len = moves.length;
        int[] dp = moves[len - 1];
        int x = 0, y = 0, x_y = 0, y_x = 0;
        int count = len - 1;
        while (count >= 0) {
            int[] cur = moves[count];
            if (cur[1] == dp[1]) x++;
            if (cur[0] == dp[0]) y++;
            if (cur[0] == cur[1]) x_y++;
            if (cur[0] + cur[1] == 2) y_x++;
            count -= 2;
        }
        if (x >= 3 || y >= 3 || x_y >= 3 || y_x >= 3) {
            return len % 2 == 0 ? "B" : "A";
        }
        if (len < 9) return "Pending";
        return "Draw";
    }
}