LeetCode1275

LeetCode1275

目次

• 题目形貌
  
• 示例
  
• 思路分析
  
• 代码段
  
• 代码逐行讲解
  
• 复杂度分析
  
• 总结的知识点
  
• 整合
  
• 总结
  

---

题目形貌

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

• 如果玩家 A 得胜，返回 "A"
  。
  
• 如果玩家 B 得胜，返回 "B"
  。
  
• 如果游戏未竣事且没有玩家得胜，返回 "ending"。
  
• 如果游戏竣事且没有玩家得胜，返回 "Draw"
  。
  

---

示例

示例 1

输入:

1. moves = [[0, 0], [2, 0], [1, 1], [2, 1], [2, 2]]

复制代码

输出:

1. "A"

复制代码

解释:

• 玩家 A 得胜，因为他在第三行形成了三连线。
  

---

示例 2

输入:

1. moves = [[0, 0], [1, 1], [0, 1], [0, 2], [1, 0], [2, 0]]

复制代码

输出:

1. "B"

复制代码

解释:

• 玩家 B 得胜，因为他在第一列形成了三连线。
  

---

示例 3

输入:

1. moves = [[0, 0], [1, 1], [2, 0], [1, 0], [1, 2], [2, 1], [0, 1], [0, 2], [2, 2]]

复制代码

输出:

1. "Draw"

复制代码

解释:

• 游戏竣事，没有玩家得胜。
  

---

思路分析

题目核心

我们必要根据玩家的落子次序，判断游戏的胜负环境。
思路拆解

• 查抄末了一步：
  
  
  
  • 查抄末了一步落子的玩家是否形成了三连线。
    
  
  
• 统计落子环境：
  
  
  
  • 统计末了一步落子的玩家在行、列、对角线上的落子数量。
    
  
  
• 判断胜负：
  
  
  
  • 如果某个方向上的落子数量达到 3，则该玩家得胜。
    
  
  
• 判断游戏状态：
  
  
  
  • 如果全部步数已满且没有玩家得胜，则返回 "Draw"
    。
    
  • 如果步数未满且没有玩家得胜，则返回 "ending"。
    
  
  

---

代码段

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;
2.         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"
3. : "A"
4. ;        }        if (len < 9) return "Pending";        return "Draw"
5. ;    }}

复制代码

---

代码逐行讲解

• 获取步数和末了一步：
  
  1. int len = moves.length;
  2. int[] dp = moves[len - 1];

  复制代码
  
  
  • 获取步数 len 和末了一步的落子位置 dp。
    
  
  
• 初始化统计变量：
  
  1. int x = 0, y = 0, x_y = 0, y_x = 0;

  复制代码
  
  
  • x 统计列方向的落子数量。
    
  • y 统计行方向的落子数量。
    
  • x_y 统计主对角线方向的落子数量。
    
  • y_x 统计副对角线方向的落子数量。
    
  
  
• 统计落子环境：
  
  1. int count = len - 1;
  2. while (count >= 0) {
  3.     int[] cur = moves[count];
  4.     if (cur[1] == dp[1]) x++;
  5.     if (cur[0] == dp[0]) y++;
  6.     if (cur[0] == cur[1]) x_y++;
  7.     if (cur[0] + cur[1] == 2) y_x++;
  8.     count -= 2;
  9. }

  复制代码
  
  
  • 从末了一步开始，每隔一步统计一次落子环境。
    
  
  
• 判断胜负：
  
  1. if (x >= 3 || y >= 3 || x_y >= 3 || y_x >= 3) {    return len % 2 == 0 ? "B"
  2. : "A"
  3. ;}

  复制代码
  
  
  • 如果某个方向上的落子数量达到 3，则返回得胜玩家。
    
  
  
• 判断游戏状态：
  
  1. if (len < 9) return "Pending";return "Draw"
  2. ;

  复制代码
  
  
  • 如果步数未满且没有玩家得胜，则返回 "ending"。
    
  • 如果步数已满且没有玩家得胜，则返回 "Draw"
    。
    
  
  

---

复杂度分析

时间复杂度

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

空间复杂度

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

---

总结的知识点

• 井字棋规则：
  
  
  
  • 明白井字棋的胜负规则和三连线的判断方法。
    
  
  
• 遍历与统计：
  
  
  
  • 通过遍历步数统计落子环境。
    
  
  
• 条件判断：
  
  
  
  • 根据统计结果判断游戏的胜负和状态。
    
  
  

---

整合

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;
2.         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"
3. : "A"
4. ;        }        if (len < 9) return "Pending";        return "Draw"
5. ;    }}

复制代码

---

总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。