LeetCode1275

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"

解释:

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

思路分析

问题核心

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

思路拆解

1. 检查最后一步：
   • 检查最后一步落子的玩家是否形成了三连线。
2. 统计落子情况：
   • 统计最后一步落子的玩家在行、列、对角线上的落子数量。
3. 判断胜负：
   • 如果某个方向上的落子数量达到 3，则该玩家获胜。
4. 判断游戏状态：
   • 如果所有步数已满且没有玩家获胜，则返回 "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";
    }
}

代码逐行讲解

1. 获取步数和最后一步：

   int len = moves.length;
   int[] dp = moves[len - 1];
   

   • 获取步数 len 和最后一步的落子位置 dp。

2. 初始化统计变量：

   int x = 0, y = 0, x_y = 0, y_x = 0;
   

   • x 统计列方向的落子数量。
   • y 统计行方向的落子数量。
   • x_y 统计主对角线方向的落子数量。
   • y_x 统计副对角线方向的落子数量。

3. 统计落子情况：

   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;
   }
   

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

4. 判断胜负：

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

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

5. 判断游戏状态：

   if (len < 9) return "Pending";
   return "Draw";
   

   • 如果步数未满且没有玩家获胜，则返回 "Pending"。
   • 如果步数已满且没有玩家获胜，则返回 "Draw"。

复杂度分析

时间复杂度

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

空间复杂度

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

总结的知识点

1. 井字棋规则：

   • 理解井字棋的胜负规则和三连线的判断方法。

2. 遍历与统计：

   • 通过遍历步数统计落子情况。

3. 条件判断：

   • 根据统计结果判断游戏的胜负和状态。

整合

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";
    }
}

总结

通过遍历和统计，能够高效地判断井字棋游戏的胜负情况。