Leetcode 794. Valid Tic-Tac-Toe State

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Valid Tic-Tac-Toe State

2. Solution

解析:Version 1,判断游戏合不合法,主要分为下面几个方面:

  1. 由于X先放,轮流放置,因此X的数量永远大于等于O的数量。
  2. 由于是轮流放置,因此二者的数量差值最大为1。
  3. X先结束游戏时,此时X的数量等于O的数量加1。
  4. O先结束游戏时,此时X的数量等于O的数量。
    根据上述条件依次判断即可。
  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
def validTicTacToe(self, board: List[str]) -> bool:
x_count = 0
o_count = 0
for line in board:
for ch in line:
if ch == 'X':
x_count += 1
elif ch == 'O':
o_count += 1
if o_count > x_count or x_count > o_count + 1:
return False
if x_count == o_count and self.isGameOver(board, 'X'):
return False
if x_count == o_count + 1 and self.isGameOver(board, 'O'):
return False

return True


def isGameOver(self, board: List[str], ch: str) -> bool:
# Check rows
for i in range(3):
if board[i][0] == ch and board[i][0] == board[i][1] and board[i][1] == board[i][2]:
return True

# Check columns
for i in range(3):
if board[0][i] == ch and board[0][i] == board[1][i] and board[1][i] == board[2][i]:
return True

# Check diagonals
if board[1][1] == ch and ((board[0][0] == board[1][1] and board[1][1] == board[2][2]) or
(board[0][2] == board[1][1] and board[1][1] == board[2][0])):
return True
return False

Reference

  1. https://leetcode.com/problems/valid-tic-tac-toe-state/
如果有收获,可以请我喝杯咖啡!