DesignTicTacToe [source code]


public class DesignTicTacToe {
static
/******************************************************************************/
class TicTacToe {
    int[][] rowCounts, colCounts;
    int[] diag1Count, diag2Count;
    int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rowCounts = new int[2][n];  //[player][index]
        colCounts = new int[2][n];
        diag1Count = new int[2];
        diag2Count = 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) {
        int p = player - 1;
        rowCounts[p][row]++;
        colCounts[p][col]++;
        if (rowCounts[p][row] == n || colCounts[p][col] == n)
            return player;
        if (row == col)
            diag1Count[p]++;
        if (row + col == n - 1) //no "else" here
            diag2Count[p]++;
        if (diag1Count[p] == n || diag2Count[p] == n)
            return player;
        return 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {

    }
}

naive的做法肯定是很简单的, 每一个move做完都直接检查一下三个方向的line就行了; 不过Follow-Up里面否定了这种做法, 那么看来就要有点办法了; 感觉历史信息流可能有用? (历史信息流算法的本质就是对之前的iteration的信息进行更高效更聪明的store, 这样后面的iteration可以更快的fetch);

这里需要注意的一个问题, 这里题目给的例子里面, move的index, 是0-based, 所以你就不需要自己还专门来一个转化了;

最后大概想了一下, 这个问题还是有思路的; 只要用count来统计历史信息就行了; 最后的速度是113ms (47%), 没有看hint, 半小时内AC, 还可以. AC之前有一个bug卡了很久, 就是在对角线hit判断的时候, 两条对角线之间不能用else来连接, 因为中点是可能同时让两条对角线的count都increment的, 如果你用了else, 那么最后就只有一个对角线被increment了;

看了一下submission最优解, 基本都是这个思路, 不知道为什么比我快; 感觉是大case的波动;

这个问题讲到底其实就是考一个点, 对这个问题本身的insight; 不要做overkill, 你要判断的只需要一个winning condition就行了: when can we call a win? envision this final result, then think;

discussion最优解: 差不多的东西, 就是解释的比较详细而已;

@bdwalker said in Java O(1) solution, easy to understand:

Initially, I had not read the Hint in the question and came up with an O(n) solution. After reading the extremely helpful hint; a much easier approach became apparent. The key observation is that in order to win Tic-Tac-Toe you must have the entire row or column. Thus, we don't need to keep track of an entire n^2 board. We only need to keep a count for each row and column. If at any time a row or column matches the size of the board then that player has won.

To keep track of which player, I add one for Player1 and -1 for Player2. There are two additional variables to keep track of the count of the diagonals. Each time a player places a piece we just need to check the count of that row, column, diagonal and anti-diagonal.

Also see a very similar answer that I believe had beaten me to the punch. We came up with our solutions independently but they are very similar in principle.
[Aeonaxx's soln][1] 

public class TicTacToe {  
     private int[] rows;  
     private int[] cols;  
     private int diagonal;  
     private int antiDiagonal;  

     public TicTacToe(int n) {  
         rows = new int[n];  
         cols = new int[n];  
     }  

     public int move(int row, int col, int player) {  
         int toAdd = player == 1 ? 1 : -1;  

         rows[row] += toAdd;  
         cols[col] += toAdd;  
         if (row == col)  
         {  
             diagonal += toAdd;  
         }  

         if (col == (cols.length - row - 1))  
         {  
             antiDiagonal += toAdd;  
         }  

         int size = rows.length;  
         if (Math.abs(rows[row]) == size ||  
             Math.abs(cols[col]) == size ||  
             Math.abs(diagonal) == size  ||  
             Math.abs(antiDiagonal) == size)  
         {  
             return player;  
         }  

         return 0;  
     }  
}

[1]: https://leetcode.com/discuss/101123/simple-o-1-time-c-solution-following-provided-hints

另外这个算法还用了一个我没有用到的小技巧来节省空间: 你有没有发现他对于row和column的counts, 都是只有一行, 也就是说不用专门分别记录比如, 每一行, 两个player的count, 只记录一个count就行了; 因为这里他move的更新(和判断)的时候用的是一个类似Moore voting的算法; 因为只有两个人, 所以这种downvote的思路是行得通的; 这个小优化还是挺有意思的;

这个是一个类似的版本: 

int[] rows, cols;  
int diagonal, anti_diagonal, target;  

public TicTacToe(int n) {  
    rows = new int[n];  
    cols = new int[n];  
    diagonal = 0;  
    anti_diagonal = 0;  
    target = n;  
}  

public int move(int row, int col, int player) {  
    int sign = player == 1 ? 1 : -1, res = sign * target;  
    rows[row] += sign;  
    cols[col] += sign;  
    if(row == col) diagonal += sign;  
    if(row == target-1-col) anti_diagonal += sign;  
    if(rows[row] == res || cols[col] == res || diagonal == res || anti_diagonal == res) return player;  
    else return 0;  
}

现在还是不是特别有把握, 什么时候可以采用downvote思路, 不过目前做过的这两题的经验来看, 以下是两个线索:

  • binary
  • count

当然, 这个只是一个浅显的总结, 严格来说, binary这个点在Moore voting里面体现的并不明显; 而且Moore voting虽然利用了downvote的思路, 但是他本身算法的复杂性还是袁不至于downvote这一个点的;

另外, Moore voting的作者自己在网站上画的一个trace是这样的: 

  A A A C C B B C C C B C C  
       ^  
      A:3

注意看他这个箭头, 也就是check point指向的对应的位置; 人家大牛想问题的时候, 在trace每一个iteration对变量更新的影响的时候, 思考的也是iteration的开头(或者说结尾), 而不是iteration正当中(和iteration本身正好对应)的时间点; 当然了, 你如果非要箭头对其iteration正当中, 也可以, 但是自己脑子里还是要先实现约定虽然我, 比如指的是C, 但是我实际上这个箭头下面的变量值到底是在C这个iteration什么时间点的? 这个要自己想好; 真正写算法的时候, 有时候就未见得有这个时间来做这个alignment的工作, 所以或许直接指向iteration之间(开头或者结尾)是一种更好的画trace的思路?

要不说美国人数学差呢, 这个都要专门说一下:

@sircodesalotOfTheRound said in Java O(1) solution, easy to understand:

One more small clarity improvement (shout out to tushar roy N-queens video for this suggestion): 

    if ((row - col) == 0) diag += toAdd;  
    if ((row + col) == (n - 1)) antidiag += toAdd;

On an n x n matrix, you can compute the (anti-)diagonal of a cell by using x + y or x - y. Since given y = mx + b, and m = {1, -1}, then y = {1, -1}x + b, thus y + {1, -1}x = b. If 'b' = 0 then it's the diagonal starting from the bottom, if 'b' = n then it's the diagonal starting from the top.

And of course, the 'b' value creates an equivalency relation, which means you can generalize this property to partition all diagonals using the 'b' value. So two spots having the same b value are on the same diagonal.

这个是Stefan的简写版本: 

public class TicTacToe {  

    public TicTacToe(int n) {  
        count = new int[6*n][3];  
    }  

    public int move(int row, int col, int player) {  
        int n = count.length / 6;  
        for (int x : new int[]{row, n+col, 2*n+row+col, 5*n+row-col})  
            if (++count[x][player] == n)  
                return player;  
        return 0;  
    }  

    int[][] count;  
}

大概就是把每一个player的所有的count都放到一个row里面去, 实际上也没有节省空间, 也没有提高readability, 反正我是不知道这个人到底追求的是什么;

注意因为player是1-based, 所以他把count的第二维度的长度设计成了3而不是2: +1技巧, 这个以前也讲过了;

Problem Description

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves is allowed.
  3. 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(n^2) per move() operation?

Difficulty:Medium
Total Accepted:14.5K
Total Submissions:31.6K
Contributor: LeetCode
Companies
microsoft google
Related Topics
design 

   Hide Hint 1    
Could you trade extra space such that move() operation can be done in O(1)?  
   Hide Hint 2    
You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

/**

  • Your TicTacToe object will be instantiated and called as such:
  • TicTacToe obj = new TicTacToe(n);
  • int param_1 = obj.move(row,col,player);
    */

results matching ""

    No results matching ""