Assume the following rules are for the tic-tac-toe game on an n x n
board between two players:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves are allowed.
- A player who succeeds in placing
n
of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe
class:
-
TicTacToe(int n)
Initializes the object the size of the boardn
. -
int move(int row, int col, int player)
Indicates that the player with idplayer
plays at the cell(row, col)
of the board. The move is guaranteed to be a valid move.
Example 1:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1] Explanation TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is "X" and player 2 is "O" in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Constraints:
2 <= n <= 100
- player is
1
or2
. 0 <= row, col < n
-
(row, col)
are unique for each different call tomove
. - At most
n2
calls will be made tomove
.
Follow-up: Could you do better than O(n2)
per move()
operation?
以上是题目,这道题我一拿到手,我想了一个非常暴力的解法,就是每次move()的时候,遍历整个board,看是否有人赢了,时间复杂度是O(n2). 但是follow-up问我们是否可以用更好的时间复杂度来解这道题。
实际上,每次move()的时候,只要check当前的player是否赢了即可,就是check 当前player的row, col, row和col对应的Diagonal 和Anti-Diagonal是否全部被当前player占领即可。
时间复杂度是O(n), 空间复杂度是O(n2), 算法如下:
private int[][] board; private int n; public TicTacToe(int n) { board = new int[n][n]; this.n = n; } public int move(int row, int col, int player) { board[row][col] = player; if(checkHorizon(row, player)) return player; if(checkVertical(col, player)) return player; if(checkDiagonal(row, col, player)) return player; if(checkAntiDiagonal(row, col, player)) return player; return 0; } private boolean checkHorizon(int row, int player){ for(int i=0;i<n;i++){ if(board[row][i]!=player) return false; } return true; } private boolean checkVertical(int col, int player){ for(int i=0;i<n;i++){ if(board[i][col]!=player) return false; } return true; } private boolean checkDiagonal(int row, int col, int player){ if(row!=col) return false; for(int i=0;i<n;i++){ if(board[i][i]!=player) return false; } return true; } private boolean checkAntiDiagonal(int row, int col, int player){ for(int i=0;i<n;i++){ if(board[i][n-i-1]!=player) return false; } return true; }
上面的算法每次都要重新去数每行,每列,每个斜线是否都被占满,那么能不能利用曾经数过的结果做个叠加呢?这样就不用每次从头数一遍了?答案是:Yes!
其实我们每次move()的时候,只要把每行,每列,每个斜线都累加起来,如果某行,某列或者某斜线的总和等于n,这个player就赢了。但是一共两个player,怎么累加呢?简单,只要用1和-1分别为两个player做累加即可。总和是n,player1赢,总和是-1,player2赢。
时间复杂度:O(1), 空间复杂度O(n), 算法如下:
class TicTacToe { int n; private int[] rows; private int[] cols; int diaNum = 0; int antiDiaNum = 0; public TicTacToe(int n) { rows = new int[n]; cols = new int[n]; this.n = n; } public int move(int row, int col, int player) { int add = player==1?1:-1; int count = player==1?n:-n; rows[row]+=add; cols[col]+=add; if(row==col){ diaNum+=add; } if(row==n-col-1){ antiDiaNum+=add; } if(rows[row]==count||cols[col]==count||diaNum==count||antiDiaNum==count) return player; return 0; } }