LeetCode 348 Design Tic-Tac-Toe

LeetCode

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

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 are allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

TicTacToe(int n) Initializes the object the size of the board n. int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Example 1:

Input
[“TicTacToe”, “move”, “move”, “move”, “move”, “move”, “move”, “move”]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is “X” and player 2 is “O” in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Constraints:

2 <= n <= 100 player is 1 or 2.
0 <= row, col < n (row, col) are unique for each different call to move.
At most n<sup>2</sup> calls will be made to move.

*Follow-up: Could you do better than O(n<sup>2</sup>) per move() operation?

题目大意：

设计井字过三关

解题思路：

游戏题。最重要是是数据结构，类似于LeetCode 051 N-Queens和LeetCode 037 Sudoku Solver用matrix记录每行，每列，对角线和反对角线的和。这样验证时候只需要O(1).

解题步骤：

N/A

注意事项：

1. 对角线和反对角线只有一条，所以要先判断move的这个点是否在对角线上。
2. 由于用-1来代表某一个player，所以判断和时候，用abs

Python代码：

class TicTacToe(TestCases):

    def __init__(self, n: int):
        self.board_len = n
        self.row = [0] * n
        self.col = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        if player == 2:
            player = -1
        self.row[row] += player
        self.col[col] += player
        if row == col: # remember
            self.diag += player
        if row == self.board_len - 1 - col:
            self.anti_diag += player
        does_win = abs(self.row[row]) == self.board_len or abs(self.col[col]) == self.board_len or \
                abs(self.diag) == self.board_len or abs(self.anti_diag) == self.board_len # remember abs
        if does_win:
            if player == -1:
                return 2
            else:
                return player
        return 0

算法分析：

move时间复杂度为O(1)，空间复杂度O(n)