1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class TicTacToe {
private int[][] rowCount;
private int[][] colCount;
private int[] diagCount;
private int[] antiDiagCount;
private int size;
public TicTacToe(int n) {
rowCount = new int[n][2];
colCount = new int[n][2];
diagCount = new int[2];
antiDiagCount = new int[2];
size = n;
}
public int move(int row, int col, int player) {
updateCount(row, col, player);
return isWin(row, col, player) ? player : 0;
}
private void updateCount(int row, int col, int player) {
rowCount[row][player - 1] += 1;
colCount[col][player - 1] += 1;
if (row == col) {
diagCount[player - 1] += 1;
}
if (row + col == size - 1) {
antiDiagCount[player - 1] += 1;
}
}
private boolean isWin(int row, int col, int player) {
return rowCount[row][player - 1] == size || colCount[col][player - 1] == size
|| diagCount[player - 1] == size || antiDiagCount[player - 1] == size;
}
}
|
最直接的想法. 就是记录每一行每一列而且两个对角线player1和player2下的子的个数. 如果在某次move后, 某一行或列或对角线该player的子的数量达到了n, 那么这个player就获胜了.
时间复杂度: O(1)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class TicTacToe {
private int[] rowCount;
private int[] colCount;
private int diagCount;
private int antiDiagCount;
private int size;
public TicTacToe(int n) {
rowCount = new int[n];
colCount = new int[n];
size = n;
}
public int move(int row, int col, int player) {
updateCount(row, col, player);
return isWin(row, col, player) ? player : 0;
}
private void updateCount(int row, int col, int player) {
int score = player == 1 ? -1 : 1;
rowCount[row] += score;
colCount[col] += score;
if (row == col) {
diagCount += score;
}
if (row + col == size - 1) {
antiDiagCount += score;
}
}
private boolean isWin(int row, int col, int player) {
int targetScore = player == 1 ? -size : size;
return rowCount[row] == targetScore || colCount[col] == targetScore
|| diagCount == targetScore || antiDiagCount == targetScore;
}
}
|
当然还能把O(n^2)直接降到O(n). 就是如果player1下子, 我们让相应的行列以及对角线(如果影响对角线的话)减去1, player2下子则加1. 那么如果某一行或列或对角线全是player1的子, 则该行或列或对角线的累积值一定是-n, 相应地, 如果是player2在某行某列或者对角线下满的话, 该行或列或对角线的累积值则是n. 这样就把时间复杂度从二次方降到了一次方.
时间复杂度: O(1)
空间复杂度: O(n)
