348. Design Tic-Tac-Toe

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, and the two players alternate in making moves. Return
• 0 if there is no winner after the move,
• 1 if player 1 is the winner after the move, or
• 2 if player 2 is the winner after the move.

思路Coding化:

class TicTacToe:

    def __init__(self, n: int):
        #變數n底下move函式會使用到
        self.n = n
        #建立row, col list
        self.row = [0]*n
        self.col = [0]*n
        #left right diagnal用來記錄斜線是否到達填入n個
        self.ldiag = 0
        self.rdiag = 0

    def move(self, row: int, col: int, player: int) -> int:
        #player1: +1 , player2: -1
        self.row[row] +=1 if player == 1 else -1
        self.col[col] +=1 if player == 1 else -1
        #判斷是否為left diagnal
        if row - col == 0:
            self.ldiag += 1 if player == 1 else -1
        #判斷是否為right diagnal
        if row + col == self.n-1:
            self.rdiag +=1 if player == 1 else -1

        #是否達到條件，如果其中一個直 橫 斜到達n，則直接return，並且看當前是哪個player
        if abs(self.row[row]) == self.n or abs(self.col[col]) == self.n or abs(self.ldiag) == self.n or abs(self.rdiag) == self.n:
            return 1 if player == 1 else 2
        #平局情況
        return 0

#T: O(1)
#S: O(N)

完整代碼:

class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.row = [0]*n
        self.col = [0]*n
        self.ldiag = 0
        self.rdiag = 0

    def move(self, row: int, col: int, player: int) -> int:
        self.row[row] +=1 if player == 1 else -1
        self.col[col] +=1 if player == 1 else -1
        if row - col == 0:
            self.ldiag += 1 if player == 1 else -1
        if row + col == self.n-1:
            self.rdiag +=1 if player == 1 else -1
        if abs(self.row[row]) == self.n or abs(self.col[col]) == self.n or abs(self.ldiag) == self.n or abs(self.rdiag) == self.n:
            return 1 if player == 1 else 2
        return 0

Time Complexity: O(1)

Space Complexity: O(N)