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.Example:Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.TicTacToe toe = new TicTacToe(3);toe.move(0, 0, 1); -> Returns 0 (no one wins)|X| | || | | | // Player 1 makes a move at (0, 0).| | | |toe.move(0, 2, 2); -> Returns 0 (no one wins)|X| |O|| | | | // Player 2 makes a move at (0, 2).| | | |toe.move(2, 2, 1); -> Returns 0 (no one wins)|X| |O|| | | | // Player 1 makes a move at (2, 2).| | |X|toe.move(1, 1, 2); -> Returns 0 (no one wins)|X| |O|| |O| | // Player 2 makes a move at (1, 1).| | |X|toe.move(2, 0, 1); -> Returns 0 (no one wins)|X| |O|| |O| | // Player 1 makes a move at (2, 0).|X| |X|toe.move(1, 0, 2); -> Returns 0 (no one wins)|X| |O||O|O| | // Player 2 makes a move at (1, 0).|X| |X|toe.move(2, 1, 1); -> Returns 1 (player 1 wins)|X| |O||O|O| | // Player 1 makes a move at (2, 1).|X|X|X|Follow up:Could you do better than O(n2) per move() operation?
Hint:
- Could you trade extra space such that
move()operation can be done in O(1)? - You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.
看了hint之后想到：既然用数组的话，一行一列都是一个element来代表，估计这个element是要用sum了，那么，能不能用sum来代表一行，使它有且只有一种可能，全部是player1完成的/全部是Player2；所以想到了是Player1就+1，是player2就-1，看最后sum是不是n，或者-n；n的情况只有一种情况这一行全是player1。因为说了不会有invalid move, 所以情况是唯一的
1 public class TicTacToe { 2 int[] rows; 3 int[] cols; 4 int diagonal; 5 int anti_diagonal; 6 int size; 7 8 /** Initialize your data structure here. */ 9 public TicTacToe(int n) {10 rows = new int[n];11 cols = new int[n];12 diagonal = 0;13 anti_diagonal = 0;14 size = n;15 }16 17 /** Player {player} makes a move at ({row}, {col}).18 @param row The row of the board.19 @param col The column of the board.20 @param player The player, can be either 1 or 2.21 @return The current winning condition, can be either:22 0: No one wins.23 1: Player 1 wins.24 2: Player 2 wins. */25 public int move(int row, int col, int player) {26 int change = (player==1? 1 : -1);27 rows[row] += change;28 cols[col] += change;29 if (row == col) diagonal += change;30 if (row + col == size-1) anti_diagonal += change;31 if (Math.abs(rows[row])==size || Math.abs(cols[col])==size || Math.abs(diagonal)==size || Math.abs(anti_diagonal)==size)32 return player;33 return 0;34 }35 }36 37 /**38 * Your TicTacToe object will be instantiated and called as such:39 * TicTacToe obj = new TicTacToe(n);40 * int param_1 = obj.move(row,col,player);41 */