Skip to content

Commit ba6a191

Browse files
fishercoder1534fishercoder1534
committed
add 348
1 parent cf7ad9f commit ba6a191

File tree

3 files changed

+67
-8
lines changed

3 files changed

+67
-8
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -155,7 +155,7 @@ Your ideas/fixes/algorithms are more than welcome!
155155
|351|[Android Unlock Patterns](https://leetcode.com/problems/android-unlock-patterns/)|[Solution](../master/src/main/java/com/stevesun/solutions/AndroidUnlockPatterns.java)| O(?)|O(?) | Medium|
156156
|350|[Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/IntersectionOfTwoArraysII.java)| O(m+n)|O((m+n)) could be optimized | Easy| HashMap, Binary Search
157157
|349|[Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/)|[Solution](../master/src/main/java/com/stevesun/solutions/IntersectionOfTwoArrays.java)| O(m+n)|O(min(m,n)) | Easy| Two Pointers, Binary Search
158-
|348|[Design Tic-Tac-Toe](https://leetcode.com/problems/design-tic-tac-toe/)|[Solution](../master/src/main/java/com/stevesun/solutions/DesignTicTacToe.java)| O(?)|O(?) | Medium|
158+
|348|[Design Tic-Tac-Toe](https://leetcode.com/problems/design-tic-tac-toe/)|[Solution](../master/src/main/java/com/stevesun/solutions/_348.java)| O(1)|O(n) | Medium| Design
159159
|346|[Moving Average from Data Stream](https://leetcode.com/problems/moving-average-from-data-stream/)|[Solution](../master/src/main/java/com/stevesun/solutions/MovingAveragefromDataStream.java)| O(1)|O(w)) | Easy| Queue
160160
|344|[Reverse String](https://leetcode.com/problems/reverse-string/)|[Solution](../master/src/main/java/com/stevesun/solutions/ReverseString.java) | O(n) |O(1) | Easy | String
161161
|343|[Integer Break](https://leetcode.com/problems/integer-break/)|[Solution](../master/src/main/java/com/stevesun/solutions/IntegerBreak.java)| O(1)|O(1) | Medium| Math

‎src/main/java/com/stevesun/solutions/DesignTicTacToe.java renamed to ‎src/main/java/com/stevesun/solutions/_348.java

Lines changed: 24 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -59,11 +59,27 @@ Could you trade extra space such that move() operation can be done in O(1)?
5959
You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.
6060
6161
*/
62-
public class DesignTicTacToe {
63-
class TicTacToe {
62+
public class _348 {
63+
//credit: https://discuss.leetcode.com/topic/44548/java-o-1-solution-easy-to-understand
64+
/**Key: in order to win a TicTacToe, you must have the entire row or column,
65+
* thus, we don't need to keep track of the entire n^2 board.
66+
* We only need to keep a count for each row and column.
67+
* If at any time, a row or column matches the size of the board, then that player has won.*/
68+
public static class TicTacToe {
6469

6570
private int diagonal;
71+
/**This is diagonal:
72+
|X| | |
73+
| |X| |
74+
| | |X|
75+
So, its condition is always like this: if (row == col)*/
76+
6677
private int antidiagonal;
78+
/**This is antidiagonal:
79+
| | |X|
80+
| |X| |
81+
|X| | |
82+
So, its condition is always like this: if (col == size - row - 1)*/
6783
private int[] rows;
6884
private int[] cols;
6985

@@ -86,18 +102,19 @@ public int move(int row, int col, int player) {
86102

87103
rows[row] += toAdd;
88104
cols[col] += toAdd;
105+
int size = rows.length;
89106

90107
if(row == col){
91108
diagonal += toAdd;
92109
}
93-
if(col == (cols.length-row-1)){
110+
if(col == (size - row - 1)){
94111
antidiagonal += toAdd;
95112
}
96113

97-
if (Math.abs(rows[row]) == rows.length
98-
|| Math.abs(cols[col]) == rows.length
99-
|| Math.abs(antidiagonal) == rows.length
100-
|| Math.abs(diagonal) == rows.length)
114+
if (Math.abs(rows[row]) == size
115+
|| Math.abs(cols[col]) == size
116+
|| Math.abs(antidiagonal) == size
117+
|| Math.abs(diagonal) == size)
101118
return player;
102119

103120
return 0;

‎src/test/java/com/stevesun/_348Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._348;
4+
import org.junit.Test;
5+
6+
import static org.junit.Assert.assertEquals;
7+
8+
/**
9+
* Created by stevesun on 5/13/17.
10+
*/
11+
public class _348Test {
12+
@Test
13+
public void test1(){
14+
int n = 3;
15+
_348.TicTacToe ticTacToe = new _348.TicTacToe(n);
16+
assertEquals(0, ticTacToe.move(0, 0, 1));
17+
assertEquals(0, ticTacToe.move(0, 2, 2));
18+
assertEquals(0, ticTacToe.move(2, 2, 1));
19+
assertEquals(0, ticTacToe.move(1, 1, 2));
20+
assertEquals(0, ticTacToe.move(2, 0, 1));
21+
assertEquals(0, ticTacToe.move(1, 0, 2));
22+
assertEquals(1, ticTacToe.move(2, 1, 1));
23+
}
24+
25+
@Test
26+
public void test2() {
27+
int n = 3;
28+
_348.TicTacToe ticTacToe = new _348.TicTacToe(n);
29+
assertEquals(0, ticTacToe.move(0, 0, 1));
30+
assertEquals(0, ticTacToe.move(1, 1, 1));
31+
assertEquals(1, ticTacToe.move(2, 2, 1));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
int n = 3;
37+
_348.TicTacToe ticTacToe = new _348.TicTacToe(n);
38+
assertEquals(0, ticTacToe.move(0, 2, 2));
39+
assertEquals(0, ticTacToe.move(1, 1, 2));
40+
assertEquals(2, ticTacToe.move(2, 0, 2));
41+
}
42+
}

0 commit comments

Comments
 (0)