LeetCode 348 Design Tic-Tac-Toe

LeetCode

<div>

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:

<pre>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| </pre>

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?

</div>

题目大意：

设计井字过三关

解题思路：

游戏题。最重要是是数据结构，类似于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)