Saturday, July 16, 2016

348. Design Tic-Tac-Toe

I solved it in naive way. The running time is O(n) which is not bad.
The top rated solution solves this problem in O(1). The idea is there is only two players and they can cancel each other.
When I revisited this problem, I made mistake in:
line 10: I missed to initialize these two members. This will lead to success for single case but failure for the whole test cases.
line 25: I missed abs() function. Since player2 adds -1 so he will win when the sum becomes -m.

1:  class TicTacToe {  
2:  private:  
3:    vector<int> rows;  
4:    vector<int> cols;  
5:    int diag;  
6:    int anti;  
7:    int m;  
8:  public:  
9:    /** Initialize your data structure here. */  
10:    TicTacToe(int n): rows(n), cols(n), m(n), diag(0), anti(0) {}  
11:    /** Player {player} makes a move at ({row}, {col}).  
12:      @param row The row of the board.  
13:      @param col The column of the board.  
14:      @param player The player, can be either 1 or 2.  
15:      @return The current winning condition, can be either:  
16:          0: No one wins.  
17:          1: Player 1 wins.  
18:          2: Player 2 wins. */  
19:    int move(int row, int col, int player) {  
20:      int a = player == 1 ? 1 : -1;  
21:      rows[row] += a;  
22:      cols[col] += a;  
23:      diag += row == col ? a : 0;  
24:      anti += row == m-1-col ? a : 0;  
25:      if (abs(rows[row]) == m || abs(cols[col]) == m || abs(diag) == m || abs(anti) == m) return player;  
26:      return 0;  
27:    }  
28:  };  
29:  /**  
30:   * Your TicTacToe object will be instantiated and called as such:  
31:   * TicTacToe obj = new TicTacToe(n);  
32:   * int param_1 = obj.move(row,col,player);  
33:   */  

No comments:

Post a Comment