LeetCode 348. Design Tic-Tac-Toe

原题链接在这里：https://leetcode.com/problems/design-tic-tac-toe/

题目：

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?

题解：

If the player wants to win after placing on current coordinate.

Either the entire row or column is this player's number.

If current coordinate is on diagonal or anti-diagonal, and entire diagonal is this player's number, player could win.

Thus have a row array, col array to track target.

d1, d2 to track diagonal and anti-diagonal. Since there is only one diagonal and one anti-diagonal.

Have player one add +1, and player two add -1.

When it hits +5, player one wins. When it hits -5, player two wins.

TIme Complexity: move, O(1).

Space: O(n).

AC Java:

 class TicTacToe {

     int [] r;

     int [] c;

     int d1;

     int d2;

     int n;

     /** Initialize your data structure here. */

     public TicTacToe(int n) {

         r = new int[n];

         c = new int[n];

         d1 = 0;

         d2 = 0;

         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) {

         int toAdd = player == 1 ? 1 : -1;

         int target = player == 1 ? n : -n;

         if(row == col){

             d1 += toAdd;

             if(d1 == target){

                 return player;

             }

         }

         if(row + col + 1 == n){

             d2 += toAdd;

             if(d2 == target){

                 return player;

             }

         }

         r[row] += toAdd;

         c[col] += toAdd;

         if(r[row] == target || c[col] == target){

             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);

  */

类似Valid Tic-Tac-Toe State.

巴特西

LeetCode 348. Design Tic-Tac-Toe

最新文章

热门文章