1275. 找出井字棋的获胜者

🟢 🔖 数组 哈希表 矩阵 模拟 🔗 力扣open in new window LeetCodeopen in new window

题目

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

Players take turns placing characters into empty squares ' '.
The first player A always places 'X' characters, while the second player B always places 'O' characters.
'X' and 'O' characters are always placed into empty squares, never on filled ones.
The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac- Toe), the grid is initially empty, and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= rowi, coli <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

题目大意

井字棋是由两个玩家 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 <= moves[i][j] <= 2
moves 里没有重复的元素。
moves 遵循井字棋的规则。

解题思路

使用一个二维数组 grid 模拟棋盘，初始化为空；
遍历 moves，按顺序将玩家的标记填入棋盘（X 或 O）；
每次填入后检查棋盘是否有获胜者，检查方式包括：
- 每行、每列是否有相同标记；
- 两条对角线是否有相同标记；
若某玩家获胜，立即返回该玩家的标记；
遍历结束后，根据是否填满棋盘判断返回 "Draw" 或 "Pending"。

复杂度分析

时间复杂度：O(1)
- 棋盘填充：需要遍历 moves，长度最大为 9，耗时 O(1)。
- 检查获胜情况：每次检查棋盘行、列和对角线，耗时 O(1)。
空间复杂度：O(1)，棋盘数组占用 3 * 3 的固定空间。

代码

/**
 * @param {number[][]} moves
 * @return {string}
 */
var tictactoe = function (moves) {
	let grid = new Array(3).fill().map(() => new Array(3).fill('')); // 初始化棋盘

	// 填充棋盘
	for (let i = 0; i < moves.length; i++) {
		const [r, c] = moves[i];
		grid[r][c] = i % 2 === 0 ? 'X' : 'O'; // 奇偶数决定玩家
	}

	// 检查获胜情况
	const check = (x) => {
		for (let i = 0; i < 3; i++) {
			// 检查行和列
			if (grid[i][0] === x && grid[i][1] === x && grid[i][2] === x) return true;
			if (grid[0][i] === x && grid[1][i] === x && grid[2][i] === x) return true;
		}
		// 检查两条对角线
		if (grid[0][0] === x && grid[1][1] === x && grid[2][2] === x) return true;
		if (grid[0][2] === x && grid[1][1] === x && grid[2][0] === x) return true;
		return false;
	};

	// 判断结果
	if (check('X')) return 'A';
	if (check('O')) return 'B';
	if (moves.length === 9) return 'Draw'; // 棋盘填满
	return 'Pending'; // 棋局未结束
};

1275. 找出井字棋的获胜者

# 1275. 找出井字棋的获胜者

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

1275. 找出井字棋的获胜者

题目

题目大意

解题思路

复杂度分析

代码

相关题目