题目
请在 n × n 的棋盘上，实现一个判定井字棋（Tic-Tac-Toe）胜负的神器，判断每一次玩家落子后，是否有胜出的玩家。
在这个井字棋游戏中，会有 2 名玩家，他们将轮流在棋盘上放置自己的棋子。
在实现这个判定器的过程中，你可以假设以下这些规则一定成立：
- 每一步棋都是在棋盘内的，并且只能被放置在一个空的格子里；
- 一旦游戏中有一名玩家胜出的话，游戏将不能再继续；
- 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子，那么他便获得胜利。
示例:
给定棋盘边长 n = 3, 玩家 1 的棋子符号是 "X"，玩家 2 的棋子符号是 "O"。
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> 函数返回 0 (此时，暂时没有玩家赢得这场对决)
|X| | |
| | | | // 玩家 1 在 (0, 0) 落子。
| | | |
toe.move(0, 2, 2); -> 函数返回 0 (暂时没有玩家赢得本场比赛)
|X| |O|
| | | | // 玩家 2 在 (0, 2) 落子。
| | | |
toe.move(2, 2, 1); -> 函数返回 0 (暂时没有玩家赢得比赛)
|X| |O|
| | | | // 玩家 1 在 (2, 2) 落子。
| | |X|
toe.move(1, 1, 2); -> 函数返回 0 (暂没有玩家赢得比赛)
|X| |O|
| |O| | // 玩家 2 在 (1, 1) 落子。
| | |X|
toe.move(2, 0, 1); -> 函数返回 0 (暂无玩家赢得比赛)
|X| |O|
| |O| | // 玩家 1 在 (2, 0) 落子。
|X| |X|
toe.move(1, 0, 2); -> 函数返回 0 (没有玩家赢得比赛)
|X| |O|
|O|O| | // 玩家 2 在 (1, 0) 落子.
|X| |X|
toe.move(2, 1, 1); -> 函数返回 1 (此时，玩家 1 赢得了该场比赛)
|X| |O|
|O|O| | // 玩家 1 在 (2, 1) 落子。
|X|X|X|
进阶:
您有没有可能将每一步的 move() 操作优化到比 O(n2) 更快吗?
分析
设计维护棋局的矩阵、维护获胜的辅助变量。
构造棋盘、落子数、遍历获胜条件
class TicTacToe {
private int[][] tcce;
private int n;
private int[] stepsPx;
public TicTacToe(int n) {
this.tcce = new int[n][n];
this.n = n;
stepsPx = new int[3];
}
public int move(int row, int col, int player) {
tcce[row][col] = player;
stepsPx[player]++;
// 玩家至少走了n步才有可能获胜
if (stepsPx[player] >= n) {
boolean finish = true;
// check col
for (int i = 0; i < n; i++) {
if (tcce[i][col] != player) {
finish = false;
break;
}
}
if (finish) {
return player;
}
// check row
finish = true;
for (int i = 0; i < n; i++) {
if (tcce[row][i] != player) {
finish = false;
break;
}
}
if (finish) {
return player;
}
// check row = col
if (row == col) {
finish = true;
for (int i = 0; i < n; i++) {
if (tcce[i][i] != player) {
finish = false;
break;
}
}
if (finish) {
return player;
}
}
// check row = n - col - 1
if (row + col == n - 1) {
finish = true;
for (int i = 0; i < n; i++) {
if (tcce[n - i - 1][i] != player) {
finish = false;
break;
}
}
}
if (finish) {
return player;
}
}
return 0;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
构造路子的内容，存储棋局获胜状态，避免遍历棋盘
玩家以落子 为 1，玩家2落子为 -1，我们存储每一行、每一列总和，对角线的总和，当和sum == n 或者 -n时，必有玩家获胜。
class TicTacToe {
/**
* 矩阵大小
*/
private final int n;
/**
* rows[i]=第i行之和
*/
private final int[] rows;
/**
* cols[j]=第j列之和
*/
private final int[] cols;
/**
* 对角线的和
*/
private int dia1, dia2;
public TicTacToe(int n) {
this.n = n;
rows = new int[n];
cols = new int[n];
dia1 = 0;
dia2 = 0;
}
/**
* 每一步放置棋子
* 时间复杂度O(1)
*/
public int move(int row, int col, int player) {
// 玩家下棋值
int cell = 1 == player ? 1 : -1;
// 玩家赢时和
int sum = 1 == player ? n : -n;
// 此行当前和
rows[row] += cell;
if (sum == rows[row]) return player;
// 此列当前和
cols[col] += cell;
if (sum == cols[col]) return player;
// 主对角线当前和
if (row == col) {
dia1 += cell;
if (sum == dia1) return player;
}
// 副对角线当前和
if (row + col == n - 1) {
dia2 += cell;
if (sum == dia2) return player;
}
return 0;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
