欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lc794. 有效的井字游戏

程序员文章站 2022-04-25 20:25:59
...

用字符串数组作为井字游戏的游戏板 board。当且仅当在井字游戏过程中,玩家有可能将字符放置成游戏板所显示的状态时,才返回 true。
原题链接

这题分到递归标签里面,但我感觉题解和递归标签不是很大啊
我用了递归遍历来判断数组相等的方法,最后超时了,结果进行剪枝优化,108个样例基本只过了80几个,但是逻辑是没问题的。
这是我的超时源码`

/**
 * description: 井字游戏
 * author: sanmu
 */
public class Solution {
    int X_sum = 0;
    int O_sum = 0;
    boolean[][] mark;
    String[] src;

    public boolean validTicTacToe(String[] board) {
        if (!preValid(board)) {
            return false;
        }
        initValue(board);
        String[] start = {"   ", "   ", "   "};
        return isValid(start, 0, 0, 'X');
    }

    private void initValue(String[] demo) {
        for (int i = 0; i < demo.length; i++) {
            for (int j = 0; j < demo[i].length(); j++) {
                if (demo[i].charAt(j) == 'X') {
                    X_sum++;
                }
                if (demo[i].charAt(j) == 'O') {
                    O_sum++;
                }
            }
            mark = new boolean[demo.length][demo[0].length()];
            src = demo;
        }
    }

    private boolean isValid(String[] start, int X_count, int O_count, char cc) {
        if(X_count >=3 || O_count>= 3){
            if(isThirdValid(start)){
                if (X_count == X_sum && O_count == O_sum) {
                    if (Arrays.equals(start, src)) {
                        return true;
                    }
                }
                return false;
            }
        }
        if (X_count == X_sum && O_count == O_sum) {
            if (Arrays.equals(start, src)) {
                return true;
            }
            return false;
        }
        for (int i = 0; i < start.length; i++) {
            for (int j = 0; j < start[0].length(); j++) {
                if (!mark[i][j]) {
                    String old = start[i];
                    StringBuilder stringBuilder = new StringBuilder(start[i]);
                    stringBuilder.setCharAt(j, cc);
                    start[i] = stringBuilder.toString();
                    mark[i][j] = true;
                    boolean flag = false;
                    if (cc == 'X') {
                        flag = isValid(start, X_count + 1, O_count, 'O');
                    } else {
                        flag = isValid(start, X_count, O_count + 1, 'X');
                    }
                    if (flag) {
                        return true;
                    }
                    mark[i][j] = false;
                    start[i] = old;
                }
            }
        }
        return false;
    }

    private boolean preValid(String[] demo) {
        boolean flag = true;
        if (O_sum > X_sum) {
            flag = false;
        }
        return flag;
    }

    private boolean isThirdValid(String[] demo) {
        int row_X = 0;
        int row_O = 0;
        int column_X = 0;
        int column_O = 0;
        int diagonal_Left_X = 0;
        int diagonal_Left_O = 0;
        int diagonal_Right_X = 0;
        int diagonal_Right_O = 0;
        for (int i = 0; i < demo.length; i++) {
            char diagonal_Left_Count = demo[i].charAt(i);
            switch (diagonal_Left_Count) {
                case 'X':
                    diagonal_Left_X++;
                    break;
                case 'O':
                    diagonal_Left_O++;
                    break;
            }
            char diagonal_Right_Count = demo[demo.length-1-i].charAt(i);
            switch (diagonal_Right_Count) {
                case 'X':
                    diagonal_Right_X++;
                    break;
                case 'O':
                    diagonal_Right_O++;
                    break;
            }
            for (int j = 0; j < demo[i].length(); j++) {
                char row_count = demo[i].charAt(j);
                char column_count = demo[j].charAt(i);
                switch (row_count) {
                    case 'X':
                        row_X++;
                        break;
                    case 'O':
                        row_O++;
                        break;
                }
                switch (column_count) {
                    case 'X':
                        column_X++;
                        break;
                    case 'O':
                        column_O++;
                        break;
                }
            }
            if (row_X == 3 || row_O == 3 || column_O == 3 || column_X == 3) {
                return true;
            }
            row_O = 0;
            row_X = 0;
            column_O = 0;
            column_X = 0;
        }
        if (diagonal_Left_O == 3 || diagonal_Left_X == 3 || diagonal_Right_O == 3 || diagonal_Right_X == 3) {
            return true;
        }
        return false;
    }
}

超时截图
lc794. 有效的井字游戏