C++刷leetcode（面试题 16.04. 井字游戏）【数据结构】

糖逗

题目描述：

设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。

以下是井字游戏的规则：

玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"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
输入一定遵循井字棋规则

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/tic-tac-toe-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    string tictactoe(vector<string>& board) {
        int len = board.size();
        string res = "Draw";
        //行
        bool flag = false;
        for(int i = 0; i < len; i++){
            stack<char> temp1;
            for(int j = 0 ;j < len; j++){
                if(board[i][j] == ' ') flag = true;
                if(temp1.empty() ){
                    temp1.push(board[i][j]);
                }else if(temp1.top() == board[i][j]){
                    temp1.push(board[i][j]);
                    if(temp1.size() == len && board[i][j] != ' '){
                        res = board[i][j];
                        return res;
                    }
                }
            }
        }
        //列
        for(int i = 0; i < len; i++){
            stack<char> temp2;
            for(int j = 0 ;j < len; j++){
                if(board[j][i] == ' ') flag = true;
                if(temp2.empty()){
                    temp2.push(board[j][i]);
                }else if(temp2.top() == board[j][i]){
                    temp2.push(board[j][i]);
                    if(temp2.size() == len &&  board[j][i] != ' '){
                        res = board[j][i];
                        return res;
                    }
                }
            }
        }
        //斜对角
        int  i = 0;
        stack<int> temp3;
        for(int j = 0 ; j < len; j++){
            if(temp3.empty() || temp3.top() == board[i][j]){
                temp3.push(board[i][j]);
            }else if(temp3.top() != board[i][j]){
                break;
            }
            i++;
        }
        if(temp3.size() == len  && temp3.top() != ' ') res = temp3.top();

        i = len - 1;
        stack<int> temp4;
        for(int j = 0; j < len; j++){
            if(temp4.empty() || temp4.top() == board[j][i]){
                temp4.push(board[j][i]);
            }else if(temp4.top() != board[j][i]){
                break;
            }
            i--;
        }

        if(temp4.size() == len && temp4.top() != ' ') res = temp4.top();
        if(res == "O" || res == "X") return res;
        else if(res == "Draw" && flag == true) return "Pending";
        return res;
    }
};

糖逗

考察对基本框架的熟练程度