LeetCode面试题16.04.井字游戏

面试题 16.04. 井字游戏
设计一个算法&＃xff0c;判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘&＃xff0c;由字符" "&＃xff0c;“X"和"O"组成&＃xff0c;其中字符” "代表一个空位。

以下是井字游戏的规则&＃xff1a;

玩家轮流将字符放入空位&＃xff08;" “&＃xff09;中。
第一个玩家总是放字符"O”&＃xff0c;且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中&＃xff0c;不允许对已放有字符的位置进行填充。
当有N个相同&＃xff08;且非空&＃xff09;的字符填充任何行、列或对角线时&＃xff0c;游戏结束&＃xff0c;对应该字符的玩家获胜。
当所有位置非空时&＃xff0c;也算为游戏结束。
如果游戏结束&＃xff0c;玩家不允许再放置字符。
如果游戏存在获胜者&＃xff0c;就返回该游戏的获胜者使用的字符&＃xff08;“X"或"O”&＃xff09;&＃xff1b;如果游戏以平局结束&＃xff0c;则返回 “Draw”&＃xff1b;如果仍会有行动&＃xff08;游戏未结束&＃xff09;&＃xff0c;则返回 “Pending”。

示例 1&＃xff1a;

输入&＃xff1a; board &＃61; [“O X”," XO",“X O”]
输出&＃xff1a; “X”
示例 2&＃xff1a;

输入&＃xff1a; board &＃61; [“OOX”,“XXO”,“OXO”]
输出&＃xff1a; “Draw”
解释&＃xff1a; 没有玩家获胜且不存在空位
示例 3&＃xff1a;

输入&＃xff1a; board &＃61; [“OOX”,“XXO”,"OX "]
输出&＃xff1a; “Pending”
解释&＃xff1a; 没有玩家获胜且仍存在空位
提示&＃xff1a;

1 <&＃61; board.length &＃61;&＃61; board[i].length <&＃61; 100
输入一定遵循井字棋规则

解法1&＃xff1a;
基于异或操作
如果某行有一个非X(空格或O)&＃xff0c;那么rowHasNonXChar 就会是true&＃xff0c;所以如果最后rowHasNonXChar是false&＃xff0c;那么说明该行都是X。
对于列&＃xff0c;主从对角线也同理。
注意第2个循环里面不能有continue&＃xff0c;否则空格就不会被考虑了&＃xff0c;那样某行有几个空格剩下全O的情况就会判O胜。

class Solution {
public:string tictactoe(vector<string>& board) {int n &＃61; board.size();bool diagHasNonXChar &＃61; false, diagHasNonOChar &＃61; false;bool revDiagHasNonXChar &＃61; false, revDiagHasNonOChar &＃61;false;bool soFarFull &＃61; true;for (int i &＃61; 0; i < n; &＃43;&＃43;i) {bool rowHasNonXChar &＃61; false, rowHasNonOChar &＃61; false;bool colHasNonXChar &＃61; false, colHasNonOChar &＃61; false;for (int j &＃61; 0; j < n; &＃43;&＃43;j) {if (soFarFull && board[i][j] &＃61;&＃61; &＃39; &＃39;) {soFarFull &＃61; false;// continue; } if (!rowHasNonXChar) rowHasNonXChar |&＃61; board[i][j] ^ &＃39;X&＃39;;if (!rowHasNonOChar) rowHasNonOChar |&＃61; board[i][j] ^ &＃39;O&＃39;;if (!colHasNonXChar) colHasNonXChar |&＃61; board[j][i] ^ &＃39;X&＃39;;if (!colHasNonOChar) colHasNonOChar |&＃61; board[j][i] ^ &＃39;O&＃39;; }if (!rowHasNonXChar || !colHasNonXChar) return "X";if (!rowHasNonOChar || !colHasNonOChar) return "O";if (!diagHasNonXChar) diagHasNonXChar |&＃61; board[i][i] ^ &＃39;X&＃39;;if (!diagHasNonOChar) diagHasNonOChar |&＃61; board[i][i] ^ &＃39;O&＃39;;if (!revDiagHasNonXChar) revDiagHasNonXChar |&＃61; board[i][n - i - 1] ^ &＃39;X&＃39;;if (!revDiagHasNonOChar) revDiagHasNonOChar |&＃61; board[i][n - i - 1] ^ &＃39;O&＃39;;}if (!diagHasNonXChar || !revDiagHasNonXChar) return "X";if (!diagHasNonOChar || !revDiagHasNonOChar) return "O";if (soFarFull) return "Draw";return "Pending";}
};