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