面试题 16.04. 井字游戏

面试题 16.04. 井字游戏"/>

面试题 16.04. 井字游戏

LeetCode： 面试题 16.04. 井字游戏

数组长度 1 <= length <= 100

暴力应该能过 >> 数据范围再大点 就 过不了了

暴力：
找到规律 >> 井字棋盘 >> 对角线 可以转换为两条直线 >> 以左上角为 （0，0） 坐标

所以从坐上到右下的对角线 的 直线方程就为： y = x

右上到左下的对角线的直线方程就为： y = -x + (len - 1)

不在上面两个直线方程里的坐标就不需要遍历对角线上的点 >> 因为其他点上的对角线必不能赢

通过定义两个 boolean 变量 >> 只需要进行一次 对角线的遍历 >> 之后就不需要再重复遍历 。

时间复杂度应该是 O(n^2) 往上

解法

1. 暴力双循环 + 条件控制
2. 求和思想 （行、列、对角线）
3. 位运算

对角线优化
[i][i]
[i][len - 1 - i]

双重循环 + 条件控制

public String tictactoe(String[] board) {int sum = 0;int x = 0;int o = 0;int len = board.length;// 两条对角线boolean yx = true;boolean yxand = true;// O(n^2)for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {char c = board[i].charAt(j);if(c == 'X' || c == 'O'){sum++;int k = 0;// 行for (k = 0; k < len; k++) {if(board[i].charAt(k) != c) break ;}if(k >= len) return c + "";// 列for (k = 0; k < len; k++) {if(board[k].charAt(j) != c) break ;}if(k >= len) return c + "";// 对角线// 稍微判断 中心点boolean b = (j != i) && (j != (len - 1 - i));if(b) continue ;if(yx && j == i){int row = 0;while (row < len){if(board[row].charAt(row++) != c){// 不相等，这条对角线玩完了yx = false;}}}if(yx && j == i) return c + "";if(yxand && j != i){int row = 0;for (int l = len - 1; l >= 0; l--) {if(board[row++].charAt(l) != c){yxand = false;}}}if(yxand && j != i) return c + "";}}}if(sum == len*len) return "Draw";return "Pending";}

上面的行、列判断还能小优化一下

空间换时间

定义行、列 boolean 数组 用来记录当前行、列是否可能赢得游戏

    boolean[] brow = new boolean[len];boolean[] bcol = new boolean[len];

若当前行 / 列有不相同的元素 >> 必不能赢，之后该行 / 该列是不需要重复判断了

if(!brow[i]) {// 行for (k = 0; k < len; k++) {if (board[i].charAt(k) != c) {brow[i] = true; break ;}}if (k >= len) return c + "";}if(!bcol[j]){// 列for (k = 0; k < len; k++) {if(board[k].charAt(j) != c) {bcol[j] = true;break ;}}if(k >= len) return c + "";}

---

求和的思想

// 求和的思想public String tictactoe(String[] board) {int len = board.length;int yxsum = 0;int yxandsum = 0;boolean isFull = true;for (int i = 0; i < len; i++) {int rowtemp = 0;int coltemp = 0;for (int j = 0; j < len; j++) {// 一行if(isFull && (board[i].charAt(j) == ' ' || board[j].charAt(i) == ' ')) isFull = false;rowtemp += board[i].charAt(j);coltemp += board[j].charAt(i);// 对角线if(i == j){yxsum += board[i].charAt(i);}if(j == (-i + len - 1)){yxandsum += board[i].charAt(j);}}// 一行if(rowtemp == len * 'X') return "X";if(rowtemp == len * 'O') return "O";// 一列if(coltemp == len * 'X') return "X";if(coltemp == len * 'O') return "O";}if(yxsum == len * 'X') return "X";if(yxsum == len * 'O') return "O";if(yxandsum == len * 'X') return "X";if(yxandsum == len * 'O') return "O";if (isFull) return "Draw";return "Pending";}

---

位运算

位运算 —> 异或

需要知道
当两个相同时 >> 异或结果为 false
当两个不同时 >> 异或结果为 true

当rowx等一直为 false 的时候 >> 就是一直为相同的 >> 当 被赋值为 true 后 >> 则这行 / 列 / 对角线 就不需要再进行计算了

public String tictactoe(String[] board) {int len = board.length;boolean yxx = false, yxo = false;boolean yxandx = false, yxando = false;boolean isFull = true;for (int i = 0; i < len; i++) {// 行、列boolean rowx = false, rowo = false;boolean colx = false, colo = false;for (int j = 0; j < len; j++) {if(isFull && (board[i].charAt(j) == ' ' || board[j].charAt(i) == ' ')) isFull = false;// 行if(!rowx) rowx =  ('X' ^ board[i].charAt(j)) != 0;if(!rowo) rowo = ('O' ^ board[i].charAt(j)) != 0;// 列if(!colx) colx = ('X' ^ board[j].charAt(i)) != 0;if(!colo) colo =  ('O' ^ board[j].charAt(i)) != 0;// 对角线if(!yxx) yxx = ('X' ^ board[i].charAt(i)) != 0;if(!yxo) yxo = ('O' ^ board[i].charAt(i)) != 0;if(!yxandx) yxandx = ('X' ^ board[i].charAt(len - 1 - i)) != 0;if(!yxando) yxando = ('O' ^ board[i].charAt(len - 1 - i)) != 0;}if(!rowx) return "X";if(!rowo) return "O";if(!colx) return "X";if(!colo) return "O";}if(!yxx) return "X";if(!yxo) return "O";if(!yxandx) return "X";if(!yxando) return "O";if(isFull) return "Draw";return "Pending";}