难度: Medium
Submission
运行时间: 56 ms
内存: 0.0 MB
class TicTacToe:
def __init__(self, n: 'int'):
"""
Initialize your data structure here.
"""
self._n = n
self._row = [[n]*n, [n]*n]
self._col = [[n]*n, [n]*n]
self._diag = [n, n, n, n]
def move(self, row: 'int', col: 'int', player: 'int') -> 'int':
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
"""
player -= 1
self._row[player][row] -= 1
if self._row[player][row] == 0:
return player+1
self._col[player][col] -= 1
if self._col[player][col] == 0:
return player+1
if row == col:
if player == 0:
self._diag[player] -= 1
if self._diag[player] == 0:
return player+1
else:
self._diag[player] -= 1
if self._diag[player] == 0:
return player+1
if row + col == self._n-1:
if player == 0:
self._diag[player+2] -= 1
if self._diag[player+2] == 0:
return player+1
else:
self._diag[player+2] -= 1
if self._diag[player+2] == 0:
return player+1
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
Explain
这个题解使用了一种巧妙的方法来判断井字棋的获胜条件。它维护了三个数组：_row 表示每一行上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜，_col 表示每一列上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜，_diag 表示在两条对角线上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜。每当一个玩家在某个位置放置棋子时，对应的 _row、_col 和 _diag 的计数就会减 1。当其中任何一个计数减为 0 时，就表示该玩家在对应的行、列或对角线上达成了获胜条件。
时间复杂度: O(1)
空间复杂度: O(n)
class TicTacToe:
def __init__(self, n: int):
"""
Initialize your data structure here.
:param n: the size of the board
"""
self._n = n
# 用于记录每一行上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜
self._row = [[n]*n, [n]*n]
# 用于记录每一列上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜
self._col = [[n]*n, [n]*n]
# 用于记录在两条对角线上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜
# _diag[0] 和 _diag[1] 对应主对角线，_diag[2] 和 _diag[3] 对应反对角线
self._diag = [n, n, n, n]
def move(self, row: int, col: int, player: int) -> int:
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
"""
player -= 1
# 更新该行上对应玩家还需要的棋子数
self._row[player][row] -= 1
if self._row[player][row] == 0:
return player+1
# 更新该列上对应玩家还需要的棋子数
self._col[player][col] -= 1
if self._col[player][col] == 0:
return player+1
# 如果落子位置在主对角线上，更新主对角线上对应玩家还需要的棋子数
if row == col:
if player == 0:
self._diag[player] -= 1
if self._diag[player] == 0:
return player+1
else:
self._diag[player] -= 1
if self._diag[player] == 0:
return player+1
# 如果落子位置在反对角线上，更新反对角线上对应玩家还需要的棋子数
if row + col == self._n-1:
if player == 0:
self._diag[player+2] -= 1
if self._diag[player+2] == 0:
return player+1
else:
self._diag[player+2] -= 1
if self._diag[player+2] == 0:
return player+1
# 如果没有玩家获胜，返回 0
return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
Explore
在井字棋游戏中，每行或每列获胜的条件是某一玩家的棋子填满整行或整列。因此，初始化时将_row和_col数组的每个元素设置为棋盘的大小n，表示每行或每列最开始时需要n个同一玩家的棋子才能获胜。这直接反映了棋盘的大小，每行或每列最大的棋子数量就是n。
在move函数中，通过对输入的row和col的值进行检查确保它们在有效范围内（即0到n-1），从而避免_row和_col数组越界。对于_diag数组，它被设计为只有四个元素，分别对应两条对角线上的胜利条件。对这些元素的访问是基于落子的位置：如果落在主对角线（row == col）或反对角线（row + col == n-1），则分别检查并更新_diag数组中的对应元素。这种方法确保了访问不会越界，因为对数组元素的访问是条件性的，只在落子位置满足对应对角线条件时发生。
设计中分别设置四个指标来跟踪两条对角线上的状态，这是为了能够独立地跟踪每个玩家在每条对角线上的胜利条件。这种设计允许系统即时检测到任一玩家在任一对角线上达到获胜条件，同时也简化了每次落子后的胜利判断逻辑。如果使用更简化的方法，可能需要更复杂的逻辑来区分不同玩家对同一对角线的影响，从而增加了实现的复杂度和出错的可能。
move函数中，当任一胜利条件的计数减至0时（即某行、列或对角线上玩家的棋子数量填满），函数就会返回该玩家的胜利状态。这是因为每次只有一个玩家可以落子，所以每次落子后只需要检查落子的玩家是否满足胜利条件。这种方法不会遗漏其他玩家的胜利情况，因为在任何玩家获胜时游戏就已经结束，不会再有进一步的落子。