ValidTicTacToeState [source code]
public class ValidTicTacToeState {
static
/******************************************************************************/
class Solution {
public boolean validTicTacToe(String[] _board) {
char[][] board = new char[3][];
for (int i = 0; i < 3; i++)
board[i] = _board[i].toCharArray ();
int count_x = 0, count_o = 0;
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
if (board[i][j] == 'X')
count_x++;
else if (board[i][j] == 'O')
count_o++;
}
if (count_x - count_o > 1 || count_o - count_x > 0)
return false;
boolean finished_x = false, finished_o = false;
for (int i = 0; i < 3; i++) {
boolean row_finished = board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] != ' ';
if (row_finished) {
if (finished_x || finished_o)
return false;
if (board[i][0] == 'X')
finished_x = true;
else
finished_o = true;
}
boolean col_finished = board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[0][i] != ' ';
if (col_finished) {
if (finished_x || finished_o)
return false;
if (board[0][i] == 'X')
finished_x = true;
else
finished_o = true;
}
}
boolean main_diag_finished = board[1][1] == board[0][0] && board[1][1] == board[2][2] && board[0][0] != ' ';
if (main_diag_finished) {
if (finished_x || finished_o)
return false;
if (board[0][0] == 'X')
finished_x = true;
else
finished_o = true;
}
boolean other_diag_finished = board[1][1] == board[0][2] && board[1][1] == board[2][0] && board[2][0] != ' ';
if (other_diag_finished) {
if (finished_x || finished_o)
return false;
if (board[0][2] == 'X')
finished_x = true;
else
finished_o = true;
}
if (count_x == count_o && finished_x)
return false;
if (finished_o && count_o < count_x)
return false;
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
ValidTicTacToeState.Solution tester = new ValidTicTacToeState.Solution();
String[][] inputs = {
{" "," "," "}, {"true"},
{"XXX","XOO","OO "}, {"false"},
{"OXX","XOX","OXO"}, {"false"},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String[] board = inputs[2 * i];
boolean ans = inputs[2 * i + 1][0].equals ("true");
boolean output = tester.validTicTacToe (board);
System.out.printf ("%s -> %s, expected: %b\n",
String.join ("|\n", board), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
最后基本是break出来的代码, 速度是8ms (NA);
editorial
Approach #1: Ad-Hoc [Accepted]
Intuition
Let's try to think about the necessary conditions for a tic-tac-toe board to be valid.
隐性的来说, 这个其实也就是我的思路; 思考必要条件来一个一个的排除; 虽然这种思路本质是有点弱;
- Since players take turns, the number of 'X's must be equal to or one greater than the number of 'O's.
- A player that wins has to win on the move that they make:
- If the first player wins, the number of 'X's is one more than the number of 'O's
- If the second player wins, the number of 'X's is equal to the number of 'O's.
- The board can't simultaneously have three 'X's and three 'O's in a row: once one player has won (on their move), there are no subsequent moves.
It turns out these conditions are also sufficient to check the validity of all boards. This is because we can check these conditions in reverse: in any board, either no player, one player, or both players have won. In the first two cases, we should check the previously stated counting conditions (a relationship between xCount and oCount), and this is sufficient. In the last case, it is not allowed to have both players win simultaneously, so our check was also sufficient.
这也是这个思路的一个问题, 就是你用必要条件来做, 首先如果真正面试的时候, 很容易漏掉是一个方面, 就算是你不漏掉, 最后你怎么跟面试官解释? 不是说题目做出来就行了的;
awice这里给的解释实际上很一般; 我感觉证明必要条件充分的条件就是, 反证法: 假设满足上面这种numerical的限制的时候, 假设存在这样一个board, 但是它实际上是不可能valid的(通过走步得到), 然后反证法证明这个board根本就不存在;
当然思路确实就是这个思路, 但是实际上要完成这个证明并不简单, 暂时还没有思路; 基本可能估计, 这题的discuss肯定很多人围绕证明展开讨论, 毕竟算法本身还是挺trivial的;
Algorithm
We'll count the number of 'X's and 'O's as xCount and oCount.
We'll also use a helper function win(player) which checks if that player has won. This checks the 8 horizontal, vertical, or diagonal lines of the board for if there are three in a row equal to that player.
After, we just have to check our conditions as stated above.
class Solution {
public boolean validTicTacToe(String[] board) {
int xCount = 0, oCount = 0;
for (String row: board)
for (char c: row.toCharArray()) {
if (c == 'X') xCount++;
if (c == 'O') oCount++;
}
if (oCount != xCount && oCount != xCount - 1) return false;
if (win(board, 'X') && oCount != xCount - 1) return false;
if (win(board, 'O') && oCount != xCount) return false;
return true;
}
public boolean win(String[] B, char P) {
// B: board, P: player
for (int i = 0; i < 3; ++i) {
if (P == B[0].charAt(i) && P == B[1].charAt(i) && P == B[2].charAt(i))
return true;
if (P == B[i].charAt(0) && P == B[i].charAt(1) && P == B[i].charAt(2))
return true;
}
if (P == B[0].charAt(0) && P == B[1].charAt(1) && P == B[2].charAt(2))
return true;
if (P == B[0].charAt(2) && P == B[1].charAt(1) && P == B[2].charAt(0))
return true;
return false;
}
}
思路几乎就跟我的差不多, 就是写法精简了一下; 他主函数的最后两行就是我的函数最后主动加上去的两个在finished之后比较count的操作;
https://leetcode.com/problems/valid-tic-tac-toe-state/discuss/117638/Easy-to-understand-in-C
bool validTicTacToe(char** board, int n) {
int x_row_count[3] = {0}, x_col_count[3] = {0};
int o_row_count[3] = {0}, o_col_count[3] = {0};
int diag1_x = 0, diag1_o = 0, diag2_x = 0, diag2_o = 0;
int i, j, x = 0, o = 0;
bool x_wins = false, o_wins = false;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(board[i][j] == 'X'){
x_row_count[i]++;
x_col_count[j]++;
if(i == j) diag1_x++;
if(i+j == 2) diag2_x++;
x++;
} else if (board[i][j] == 'O'){
o_row_count[i]++;
o_col_count[j]++;
if(i == j) diag1_o++;
if(i+j == 2) diag2_o++;
o++;
}
if((x_row_count[i] == 3) || (x_col_count[j] == 3) ||
(diag1_x == 3) || (diag2_x == 3)) x_wins = true;
if((o_row_count[i] == 3) || (o_col_count[j] == 3) ||
(diag1_o == 3) || (diag2_o == 3)) o_wins = true;
}
}
// x should be equal to o or 1 greater than o as x always starts the game
if(!((x == o) || (x == o+1))) return false;
//if x wins, count of x should be greater than o
if(x_wins && (x <= o)) return false;
//if o wins, count of x should be equal to o
if(o_wins && (x!= o)) return false;
return true;
}
1pass的做法, 核心思路还是差不多的;
When turns is 1, X moved. When turns is 0, O moved.
rows stores the number of X or O in each row. cols stores the number of X or O in each column. diag stores the number of X or O in diagonal. antidiag stores the number of X or O in antidiagonal. When any of the value gets to 3, it means X wins. When any of the value gets to -3, it means O wins.
When X wins, O cannot move anymore, so turns must be 1. When O wins, X cannot move anymore, so turns must be 0. Finally, when we return, turns must be either 0 or 1, and X and O cannot win at same time.
class Solution {
public boolean validTicTacToe(String[] board) {
int turns = 0;
boolean xwin = false;
boolean owin = false;
int[] rows = new int[3];
int[] cols = new int[3];
int diag = 0;
int antidiag = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i].charAt(j) == 'X') {
turns++;
rows[i]++;
cols[j]++;
if (i == j) {
diag++;
}
if (i + j == 2) {
antidiag++;
}
} else if (board[i].charAt(j) == 'O') {
turns--;
rows[i]--;
cols[j]--;
if (i == j) {
diag--;
}
if (i + j == 2) {
antidiag--;
}
}
}
}
xwin = rows[0] == 3 || rows[1] == 3 || rows[2] == 3 ||
cols[0] == 3 || cols[1] == 3 || cols[2] == 3 ||
diag == 3 || antidiag == 3;
owin = rows[0] == -3 || rows[1] == -3 || rows[2] == -3 ||
cols[0] == -3 || cols[1] == -3 || cols[2] == -3 ||
diag == -3 || antidiag == -3;
if (xwin && turns == 0 || owin && turns == 1) {
return false;
}
return (turns == 0 || turns == 1) && (!xwin || !owin);
}
}
用一个turns来完成对最后的判断的帮助, 这个实际上跟比较x和o的count是差不多的意思, 不过这样的做法确实更elegant一点;
submission没有;
uwi做法:
看看就行了, 速度是215ms, 这个就是竞赛的时候瞎写的一个东西;
class Solution {
public boolean validTicTacToe(String[] board) {
char[] map = new char[9];
for(int i = 0;i < 3;i++){
for(int j = 0;j < 3;j++){
map[i*3+j] = board[i].charAt(j);
}
}
int ox = 0;
for(int i = 0;i < 9;i++){
if(map[i] != ' ')ox++;
}
int[] ord = new int[9];
for(int i = 0;i < 9;i++)ord[i] = i;
outer:
do{
for(int j = 0;j < ox;j++){
if(map[ord[j]] != (j%2 == 0 ? 'X' : 'O')){
continue outer;
}
}
char[] t = new char[9];
Arrays.fill(t, ' ');
for(int j = 0;j < ox-1;j++){
t[ord[j]] = map[ord[j]];
if(end(t))continue outer;
}
return true;
}while(nextPermutation(ord));
return false;
}
int[][] q = {
{0, 1, 2},
{3, 4, 5},
{6, 7, 8},
{0, 3, 6},
{1, 4, 7},
{2, 5, 8},
{0, 4, 8},
{2, 4, 6}
};
boolean end(char[] t)
{
for(int[] o : q){
if(t[o[0]] != ' ' && t[o[0]] == t[o[1]] && t[o[1]] == t[o[2]])return true;
}
return false;
}
public boolean nextPermutation(int[] a) {
int n = a.length;
int i;
for (i = n - 2; i >= 0 && a[i] >= a[i + 1]; i--)
;
if (i == -1)
return false;
int j;
for (j = i + 1; j < n && a[i] < a[j]; j++)
;
int d = a[i];
a[i] = a[j - 1];
a[j - 1] = d;
for (int p = i + 1, q = n - 1; p < q; p++, q--) {
d = a[p];
a[p] = a[q];
a[q] = d;
}
return true;
}
}
还真的是用recursion去做了的样子;
看了这个, 我才回想起来我对next permutation好像实际上掌握的并不充分, 应该是三个阶段:
- 从右到左, 找到第一个downtick, 这个downtick的左端点就是要往后插入的数字;
- 在插入数字的右边找到第一个比[i] leq的数字, 是swap出去的数字[j-1], 注意看这里是包含等号的; 然后和插入数字进行交换;
- 这里为什么要包含等号? swap相等的不是等于无用功吗? 比如
1 3 5 3 2, 不对, 其实无所谓, 就算是你这swap了两个3, 下一个阶段是reverse5 3 2, 最后还是能得到一个新的permutation; 这里之所以一看到等号(而不一定是严格小于)就停下来, 是因为假如我们最后实际上swap的是[1]和[4], 得到1 2 5 3 3, 然后reverse, 得到的是1 2 3 3 5, 这个实际上就错了, 因为这个permutation实际上是回去了, 是比之前的1 3 5 3 2还要小了; 所以等号的时候就要停下来;
- 这里为什么要包含等号? swap相等的不是等于无用功吗? 比如
- 第三阶段也就是我忘记的, 要把插入点右边直到末尾的全部都reverse一下;
注意他这里这个写法是包含了对有duplicate的情况的处理的, 注意看他第一阶段找downtick的时候不找等号的tick;
花了点时间, 大概看懂了, 首先他这里的permutation就是完成一个类似, 比如原来这个[9]的array是一个排列, 现在我要让所有的cell都换位置, 那么如果是两个cell, 我们一般用swap就行了, 但是这里有9个, 所以他就用一个permute mapping的方法, ord是加在原来的index上面的一层indirection, 通过对这个ord的permute就可以完成类似对整个board进行shuffle的操作;
他的核心逻辑就是, 先有了这个board, 然后不停的shuffle, 一直shuffle成XOXO...这样交替, 并且X开头的序列, 然后进行一个判断;
这个算是把一个不确定性转化为确定性的思路: 我们不知道这个棋盘是什么样的, 但是既然是一个交替下棋的, 那么我们就让他们交替, 然后看看是否valid;
这样一个逻辑背后需要的一个assumption就是, shuffle一个棋盘不会对他的validity产生影响. 其实如果能理解到这一步, 当初就可以直接用count来做了;
另外即使是按照他这个逻辑来写, 他的代码的组织也不是最后, 尤其是outer那里, 完全没有必要写到一个循环里面去, 分成两步: shuffle到交替结构, 然后判断end, 会更加清晰一点;
那么, 你怎么证明shuffle对一个棋盘的validity没有影响呢? 感觉这个assumption的证明实际上对于我们普通的数值分析的解法也有帮助;
另外, 对于do-while的continue的行为我不太熟悉:
int i = 0;
do {
System.out.println (i);
if (i % 3 == 0)
continue;
} while (++i < 10);
输出:
0
1
2
3
4
5
6
7
8
9
所以这个continue是实际上会执行header里面的内容的; 这个跟普通的for循环的continue的行为实际上是类似的, 不过因为do-while的写法, 看起来不太直观;
回头想了一下, 他这里outer里面的逻辑是对的: 首先证明现在的shuffle, 是一个合理的XOXO...结构, 这个是因为下棋的本质决定的; 但是这里还没有考虑因为finished的情况带来的invalid情况; 然后他再来比较, 除了最后一个棋子之外的, 前面的0..ox-1, 是否已经finished, 如果已经finished, 那么最后ox这个棋子就肯定是有问题的; 这时候他下一步的动作是重新permute: 注意, 这样得到的下一次通过XO判断的board, 虽然序列化之后的Map是跟当前的board的Map是一样的, 但是并不是一样的board: 二维结构不一样; 同样的XOXOXOXO, 很可能有的对应的board就是还没有finished, 有的对应的就是已经finished的;
感觉这题来说uwi的逻辑用的算是相当的复杂了;
另外前面说的那个shuffle不影响validity的假定, 好像并不成立, 只是不影响交替结构的成立而已, 而这个是很trivial的; 在判断交替结构的限制满足之后, 还要额外判断finished的validity;
Problem Description
A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
- Players take turns placing characters into empty squares (" ").
- The first player always places "X" characters, while the second player always places "O" characters.
- "X" and "O" characters are always placed into empty squares, never filled ones.
- The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
- The game also ends if all squares are non-empty.
- No more moves can be played if the game is over.
Example 1:
Input: board = ["O ", " ", " "]
Output: false
Explanation: The first player always plays "X".
Example 2:
Input: board = ["XOX", " X ", " "]
Output: false
Explanation: Players take turns making moves.
Example 3:
Input: board = ["XXX", " ", "OOO"]
Output: false
Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true
Note:
- board is a length-3 array of strings, where each string board[i] has length 3.
- Each board[i][j] is a character in the set {" ", "X", "O"}.
Difficulty:Medium
Total Accepted:963
Total Submissions:4.3K
Contributor:ngoc_lam
Companies
microsoft
Related Topics
mathrecursion