LeetCode刷题实战348：设计井字棋
共 6733字，需浏览 14分钟
·
2021-08-11 13:58
Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
示例
示例:
给定棋盘边长 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(n^2) 更快吗?
解题
class TicTacToe {
private int[] rows;
private int[] cols;
private int[] dig;
// 棋盘的大小为 n × n
private int n;
/**
* Initialize your data structure here.
*/
public TicTacToe(int n) {
rows = new int[n];
cols = new int[n];
dig = new int[2];
this.n = n;
}
/**
* Player {player} makes a move at ({row}, {col}).
*
* @param row The row of the board.
* @param col The column of the board.
* @param player The player, can be either 1 or 2.
* @return The current winning condition, can be either:
* 0: No one wins.
* 1: Player 1 wins.
* 2: Player 2 wins.
*/
public int move(int row, int col, int player) {
boolean gameOver = false;
if (player == 1) { // 1 号玩家
rows[row]++; // 1 号玩家在这一行新加了一个棋子，用 +1 表示
cols[col]++;
if (row == col) dig[0]++;
if (row + col == n - 1) dig[1]++;
gameOver = rows[row] == n || // 若第 row 行全是玩家 1 的棋子，那么 rows[row] 的值就是 n
cols[col] == n || // 若第 col 行全是玩家 1 的棋子，那么 cols[col] 的值就是 n
(row == col && dig[0] == n) || // 若左上到右下全是玩家 1 的棋子，那么 dig[0] 的值就是 n
(row + col == n - 1 && dig[1] == n); // 若右上到左下全是玩家 1 的棋子，那么 dig[1] 的值就是 n
return gameOver ? player : 0;
} else { // 2 号玩家
rows[row]--; // 2 号玩家在这一行新加了一个棋子，用 -1 表示
cols[col]--;
if (row == col) dig[0]--;
if (row + col == n - 1) dig[1]--;
gameOver = rows[row] == -n ||
cols[col] == -n ||
(row == col && dig[0] == -n) ||
(row + col == n - 1 && dig[1] == -n);
return gameOver ? player : 0;
}
}
}