Easy

题目描述

井字棋是由两名玩家 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 <= 9
  • moves[i].length == 2
  • 0 <= rowi, coli <= 2
  • moves 中没有重复的元素
  • moves 遵循井字棋的规则

解题思路

这道题要求我们模拟井字棋游戏并判断结果。解题思路分为以下几个步骤：

基本思路：

  1. 首先重建棋盘状态：根据moves数组逐步在3x3棋盘上放置棋子，奇数位置是A（‘X’），偶数位置是B（‘O’）
  2. 判断获胜条件：检查所有行、列和对角线是否有三个相同的棋子
  3. 返回结果：如果有获胜者返回对应玩家，如果棋盘满了但无获胜者返回"Draw”，否则返回"Pending"

优化思路： 可以不用真正构建棋盘，而是使用计数的方式。对于每个玩家，维护行、列、对角线的计数器。当某个计数器达到3时，该玩家获胜。这样可以边放置棋子边检查获胜条件，提前结束游戏。

推荐解法： 使用计数器的优化方法，时间复杂度更优，代码也更简洁。每次放置棋子后立即检查是否获胜，避免了最后遍历整个棋盘的开销。

代码实现

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        vector<int> rows(3, 0), cols(3, 0);
        int diag = 0, anti_diag = 0;
        
        for (int i = 0; i < moves.size(); i++) {
            int r = moves[i][0], c = moves[i][1];
            int player = (i % 2 == 0) ? 1 : -1;
            
            rows[r] += player;
            cols[c] += player;
            if (r == c) diag += player;
            if (r + c == 2) anti_diag += player;
            
            if (abs(rows[r]) == 3 || abs(cols[c]) == 3 || 
                abs(diag) == 3 || abs(anti_diag) == 3) {
                return (player == 1) ? "A" : "B";
            }
        }
        
        return (moves.size() == 9) ? "Draw" : "Pending";
    }
};

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows, cols = [0] * 3, [0] * 3
        diag = anti_diag = 0
        
        for i, (r, c) in enumerate(moves):
            player = 1 if i % 2 == 0 else -1
            
            rows[r] += player
            cols[c] += player
            if r == c:
                diag += player
            if r + c == 2:
                anti_diag += player
            
            if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
                return "A" if player == 1 else "B"
        
        return "Draw" if len(moves) == 9 else "Pending"

public class Solution {
    public string Tictactoe(int[][] moves) {
        int[] rows = new int[3], cols = new int[3];
        int diag = 0, antiDiag = 0;
        
        for (int i = 0; i < moves.Length; i++) {
            int r = moves[i][0], c = moves[i][1];
            int player = (i % 2 == 0) ? 1 : -1;
            
            rows[r] += player;
            cols[c] += player;
            if (r == c) diag += player;
            if (r + c == 2) antiDiag += player;
            
            if (Math.Abs(rows[r]) == 3 || Math.Abs(cols[c]) == 3 || 
                Math.Abs(diag) == 3 || Math.Abs(antiDiag) == 3) {
                return (player == 1) ? "A" : "B";
            }
        }
        
        return (moves.Length == 9) ? "Draw" : "Pending";
    }
}

var tictactoe = function(moves) {
    const board = Array(3).fill().map(() => Array(3).fill(''));
    
    for (let i = 0; i < moves.length; i++) {
        const [row, col] = moves[i];
        board[row][col] = i % 2 === 0 ? 'A' : 'B';
        
        if (checkWinner(board, row, col, board[row][col])) {
            return board[row][col];
        }
    }
    
    return moves.length === 9 ? "Draw" : "Pending";
};

function checkWinner(board, row, col, player) {
    if (board[row][0] === player && board[row][1] === player && board[row][2] === player) return true;
    if (board[0][col] === player && board[1][col] === player && board[2][col] === player) return true;
    if (row === col && board[0][0] === player && board[1][1] === player && board[2][2] === player) return true;
    if (row + col === 2 && board[0][2] === player && board[1][1] === player && board[2][0] === player) return true;
    return false;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)n为moves的长度，最多9步，每步检查获胜条件为O(1)
空间复杂度O(1)只使用固定大小的数组存储行列对角线计数

相关题目