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;
}
}
超时截图