class Solution {
public:
string tictactoe(vector<string>& board) {
}
};
面试题 16.04. 井字游戏
设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
以下是井字游戏的规则：
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
示例 1：
输入： board = ["O X"," XO","X O"] 输出： "X"
示例 2：
输入： board = ["OOX","XXO","OXO"] 输出： "Draw" 解释： 没有玩家获胜且不存在空位
示例 3：
输入： board = ["OOX","XXO","OX "] 输出： "Pending" 解释： 没有玩家获胜且仍存在空位
提示：
1 <= board.length == board[i].length <= 100原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 39 MB, 提交时间: 2022-11-30 22:22:12
class Solution {
public String tictactoe(String[] board) {
int N = board.length;
//行的值，列的值，主对角线的值，副对角线的值
int rows = 0, cols = 0, dig1 = 0, dig2 = 0;
boolean f = false;//判断是否有空格
for (int i = 0; i < N; i++) {
rows = 0;
cols = 0;
dig1 += board[i].charAt(i);
dig2 += board[i].charAt(N - 1 - i);
for (int j = 0; j < N; j++) {
rows += board[i].charAt(j);
cols += board[j].charAt(i);
if (board[i].charAt(j) == ' ') f = true;
}
//判断行列
if (rows == 'X' * N || cols == 'X' * N) return "X";
else if (rows == 'O' * N || cols == 'O' * N) return "O";
}
//判断主对角线 X先手
if (dig1 == 'X' * N || dig2 == 'X' * N) return "X";
if (dig1 == 'O' * N || dig2 == 'O' * N) return "O";
if (f) return "Pending";
return "Draw";
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.8 MB, 提交时间: 2022-11-30 22:21:25
class Solution {
public:
string tictactoe(vector<string>& board) {
int N = board.size();
bool is_full = true;
bool XDiaWin = false, ODiaWin = false;
bool XiDiaWin = false, OiDiaWin = false;
for(int i=0;i<N;++i)
{
bool XRowWin = false, XColWin = false;
bool ORowWin = false, OColWin = false;
for(int j=0;j<N;++j)
{
if(is_full && board[i][j] == ' ')
{
is_full = false;
}
if(!XRowWin) XRowWin = XRowWin || ('X' ^ board[i][j]);
if(!ORowWin) ORowWin = ORowWin || ('O' ^ board[i][j]);
if(!XColWin) XColWin = XColWin || ('X' ^ board[j][i]);
if(!OColWin) OColWin = OColWin || ('O' ^ board[j][i]);
}
if(!XRowWin || !XColWin) return "X";
if(!ORowWin || !OColWin) return "O";
// diagonal
if(!XDiaWin) XDiaWin = XDiaWin || ('X' ^ board[i][i]);
if(!ODiaWin) ODiaWin = ODiaWin || ('O' ^ board[i][i]);
if(!XiDiaWin) XiDiaWin = XiDiaWin || ('X' ^ board[i][N-1-i]);
if(!OiDiaWin) OiDiaWin = OiDiaWin || ('O' ^ board[i][N-1-i]);
}
if(!XDiaWin || !XiDiaWin) return "X";
if(!ODiaWin || !OiDiaWin) return "O";
if(is_full) return "Draw";
return "Pending";
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2022-11-30 22:20:58
class Solution:
def tictactoe(self, board: List[str]) -> str:
n = len(board)
def check(c):
s = c * n
return any((
any(row == s for row in board),
any(col == s for col in map(''.join, zip(*board))),
all(board[i][i] == c for i in range(n)),
all(board[i][n - i - 1] == c for i in range(n))
))
if check('X'):
return 'X'
if check('O'):
return 'O'
if ' ' in ''.join(board):
return 'Pending'
return 'Draw'
python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-30 22:20:33
class Solution:
def tictactoe(self, board: List[str]) -> str:
n = len(board)
x_dia_win = False
x_idia_win = False
o_dia_win = False
o_idia_win = False
is_full = True
for i in range(n):
x_row_win = False
x_col_win = False
o_row_win = False
o_col_win = False
for j in range(n):
if is_full and board[i][j] == ' ':
is_full = False
if not x_row_win:
x_row_win = x_row_win == ('X' == board[i][j])
if not x_col_win:
x_col_win = x_col_win == ('X' == board[j][i])
if not o_row_win:
o_row_win = o_row_win == ('O' == board[i][j])
if not o_col_win:
o_col_win = o_col_win == ('O' == board[j][i])
if (not x_row_win) or (not x_col_win):
return "X"
if (not o_row_win) or (not o_col_win):
return "O"
if not x_dia_win:
x_dia_win = x_dia_win == ('X' == board[i][i])
if not x_idia_win:
x_idia_win = x_idia_win == ('X' == board[i][n-1-i])
if not o_dia_win:
o_dia_win = o_dia_win == ('O' == board[i][i])
if not o_idia_win:
o_idia_win = o_idia_win == ('O' == board[i][n-1-i])
if (not x_dia_win) or (not x_idia_win):
return "X"
if (not o_dia_win) or (not o_idia_win):
return "O"
if is_full:
return "Draw"
return "Pending"