设计井字棋
难度:
标签:
题目描述
代码结果
运行时间: 56 ms, 内存: 0.0 MB
/*
* 设计井字棋
* 题目思路:
* 实现一个TicTacToe类,它具备如下功能:
* 1. TicTacToe(int n) 初始化一个大小为 n 的井字棋棋盘。
* 2. int move(int row, int col, int player) 表示玩家 player 在棋盘 (row, col) 上落子。
* - player = 1 表示玩家 1,player = 2 表示玩家 2。
* - 如果玩家 player 获胜,返回 player。如果没有玩家获胜,返回 0。
*/
import java.util.stream.IntStream;
public class TicTacToe {
private int[] rows;
private int[] cols;
private int diagonal;
private int antiDiagonal;
private int n;
public TicTacToe(int n) {
this.n = n;
rows = new int[n];
cols = new int[n];
diagonal = 0;
antiDiagonal = 0;
}
public int move(int row, int col, int player) {
int toAdd = player == 1 ? 1 : -1;
rows[row] += toAdd;
cols[col] += toAdd;
if (row == col) {
diagonal += toAdd;
}
if (row + col == n - 1) {
antiDiagonal += toAdd;
}
if (IntStream.of(rows).anyMatch(x -> Math.abs(x) == n) ||
IntStream.of(cols).anyMatch(x -> Math.abs(x) == n) ||
Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) {
return player;
}
return 0;
}
}
解释
方法:
这个题解使用了一种巧妙的方法来判断井字棋的获胜条件。它维护了三个数组:_row 表示每一行上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜,_col 表示每一列上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜,_diag 表示在两条对角线上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜。每当一个玩家在某个位置放置棋子时,对应的 _row、_col 和 _diag 的计数就会减 1。当其中任何一个计数减为 0 时,就表示该玩家在对应的行、列或对角线上达成了获胜条件。
时间复杂度:
O(1)
空间复杂度:
O(n)
代码细节讲解
🦆
在初始化时,数组_row和_col中的每个元素为何设置为n,这与棋盘大小的关系是什么?
▷🦆
如何确保move函数中对数组的访问不会越界,特别是对_diag数组的操作?
▷🦆
为什么在对对角线的胜利条件检查时,分别设置了四个指标来跟踪两个玩家在两条对角线上的状态,而不是更简化的方法?
▷🦆
move函数返回的胜利状态是如何立即确定的,即检测到计数为0就直接返回胜利,这种实现有可能遗漏其他玩家的胜利情况吗?
▷相关问题
有效的井字游戏
给你一个字符串数组 board
表示井字游戏的棋盘。当且仅当在井字游戏过程中,棋盘有可能达到 board
所显示的状态时,才返回 true
。
井字游戏的棋盘是一个 3 x 3
数组,由字符 ' '
,'X'
和 'O'
组成。字符 ' '
代表一个空位。
以下是井字游戏的规则:
- 玩家轮流将字符放入空位(
' '
)中。 - 玩家 1 总是放字符
'X'
,而玩家 2 总是放字符'O'
。 'X'
和'O'
只允许放置在空位中,不允许对已放有字符的位置进行填充。- 当有 3 个相同(且非空)的字符填充任何行、列或对角线时,游戏结束。
- 当所有位置非空时,也算为游戏结束。
- 如果游戏结束,玩家不允许再放置字符。
示例 1:

输入:board = ["O "," "," "] 输出:false 解释:玩家 1 总是放字符 "X" 。
示例 2:

输入:board = ["XOX"," X "," "] 输出:false 解释:玩家应该轮流放字符。
示例 3:

输入:board = ["XOX","O O","XOX"] 输出:true
提示:
board.length == 3
board[i].length == 3
board[i][j]
为'X'
、'O'
或' '