Skip to content

Commit a5f3161

Browse files
fishercoder1534fishercoder1534
committed
refactor 331
1 parent a8a43d3 commit a5f3161

File tree

2 files changed

+82
-78
lines changed

2 files changed

+82
-78
lines changed

‎src/main/java/com/fishercoder/solutions/_331.java

Lines changed: 44 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -40,52 +40,57 @@
4040
*/
4141
public class _331 {
4242

43-
/**credit: https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution
44-
* Some used stack. Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we consider null as leaves, then
45-
all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
46-
all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).
47-
Suppose we try to build this tree.
48-
During building, we record the difference between out degree and in degree diff = outdegree - indegree.
49-
When the next node comes, we then decrease diff by 1, because the node provides an in degree.
50-
If the node is not null, we increase diff by 2, because it provides two out degrees.
51-
If a serialization is correct, diff should never be negative and diff will be zero when finished.
52-
*/
53-
public boolean isValidSerialization_clever_solution(String preorder) {
54-
String[] pre = preorder.split(",");
55-
int diff = 1;
56-
for (String each : pre) {
57-
if (diff < 0) {
58-
return false;
59-
}
60-
diff--;
61-
if (!each.equals("#")) {
62-
diff += 2;
43+
public static class Solution1 {
44+
/**
45+
* credit: https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution Some used stack.
46+
* Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we
47+
* consider null as leaves, then all non-null node provides 2 outdegree and 1 indegree (2
48+
* children and 1 parent), except root all null node provides 0 outdegree and 1 indegree (0
49+
* child and 1 parent). Suppose we try to build this tree. During building, we record the
50+
* difference between out degree and in degree diff = outdegree - indegree. When the next node
51+
* comes, we then decrease diff by 1, because the node provides an in degree. If the node is not
52+
* null, we increase diff by 2, because it provides two out degrees. If a serialization is
53+
* correct, diff should never be negative and diff will be zero when finished.
54+
*/
55+
public boolean isValidSerialization(String preorder) {
56+
String[] pre = preorder.split(",");
57+
int diff = 1;
58+
for (String each : pre) {
59+
if (diff < 0) {
60+
return false;
61+
}
62+
diff--;
63+
if (!each.equals("#")) {
64+
diff += 2;
65+
}
6366
}
67+
return diff == 0;
6468
}
65-
return diff == 0;
6669
}
6770

68-
public boolean isValidSerialization(String preorder) {
69-
/**Idea: we keep inserting the string into the stack, if it's a number, we just push it onto the stack;
70-
* if it's a "#", we see if the top of the stack is a "#" or not,
71-
* 1. if it's a "#", we pop it and keep popping numbers from the stack,
72-
* 2. if it's not a "#", we push the "#" onto the stack*/
73-
if (preorder == null || preorder.length() == 0) {
74-
return false;
75-
}
76-
String[] pre = preorder.split(",");
77-
Deque<String> stack = new ArrayDeque<>();
78-
for (int i = 0; i < pre.length; i++) {
79-
while (pre[i].equals("#") && !stack.isEmpty() && stack.peekLast().equals("#")) {
80-
stack.pollLast();
81-
if (stack.isEmpty()) {
82-
return false;
71+
public static class Solution2 {
72+
public boolean isValidSerialization(String preorder) {
73+
/**Idea: we keep inserting the string into the stack, if it's a number, we just push it onto the stack;
74+
* if it's a "#", we see if the top of the stack is a "#" or not,
75+
* 1. if it's a "#", we pop it and keep popping numbers from the stack,
76+
* 2. if it's not a "#", we push the "#" onto the stack*/
77+
if (preorder == null || preorder.length() == 0) {
78+
return false;
79+
}
80+
String[] pre = preorder.split(",");
81+
Deque<String> stack = new ArrayDeque<>();
82+
for (int i = 0; i < pre.length; i++) {
83+
while (pre[i].equals("#") && !stack.isEmpty() && stack.peekLast().equals("#")) {
84+
stack.pollLast();
85+
if (stack.isEmpty()) {
86+
return false;
87+
}
88+
stack.pollLast();
8389
}
84-
stack.pollLast();
90+
stack.addLast(pre[i]);
8591
}
86-
stack.addLast(pre[i]);
92+
return stack.size() == 1 && stack.peekLast().equals("#");
8793
}
88-
return stack.size() == 1 && stack.peekLast().equals("#");
8994
}
9095

9196
}

‎src/test/java/com/fishercoder/_331Test.java

Lines changed: 38 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -6,44 +6,43 @@
66

77
import static org.junit.Assert.assertEquals;
88

9-
/**
10-
* Created by fishercoder on 5/29/17.
11-
*/
129
public class _331Test {
13-
private static _331 test;
14-
15-
@BeforeClass
16-
public static void setup() {
17-
test = new _331();
18-
}
19-
20-
@Test
21-
public void test1() {
22-
assertEquals(true, test.isValidSerialization_clever_solution("9,3,4,#,#,1,#,#,2,#,6,#,#"));
23-
assertEquals(true, test.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
24-
}
25-
26-
@Test
27-
public void test2() {
28-
assertEquals(false, test.isValidSerialization_clever_solution("1,#"));
29-
assertEquals(false, test.isValidSerialization("1,#"));
30-
}
31-
32-
@Test
33-
public void test3() {
34-
assertEquals(false, test.isValidSerialization_clever_solution("9,#,#,1"));
35-
assertEquals(false, test.isValidSerialization("9,#,#,1"));
36-
}
37-
38-
@Test
39-
public void test4() {
40-
assertEquals(false, test.isValidSerialization_clever_solution("1"));
41-
assertEquals(false, test.isValidSerialization("1"));
42-
}
43-
44-
@Test
45-
public void test5() {
46-
assertEquals(true, test.isValidSerialization_clever_solution("#,7,6,9,#,#,#"));
47-
}
48-
10+
private static _331.Solution1 solution1;
11+
private static _331.Solution2 solution2;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _331.Solution1();
16+
solution2 = new _331.Solution2();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
assertEquals(true, solution1.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
22+
assertEquals(true, solution2.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
23+
}
24+
25+
@Test
26+
public void test2() {
27+
assertEquals(false, solution1.isValidSerialization("1,#"));
28+
assertEquals(false, solution2.isValidSerialization("1,#"));
29+
}
30+
31+
@Test
32+
public void test3() {
33+
assertEquals(false, solution1.isValidSerialization("9,#,#,1"));
34+
assertEquals(false, solution2.isValidSerialization("9,#,#,1"));
35+
}
36+
37+
@Test
38+
public void test4() {
39+
assertEquals(false, solution1.isValidSerialization("1"));
40+
assertEquals(false, solution2.isValidSerialization("1"));
41+
}
42+
43+
@Test
44+
public void test5() {
45+
assertEquals(true, solution1.isValidSerialization("#,7,6,9,#,#,#"));
46+
assertEquals(true, solution2.isValidSerialization("#,7,6,9,#,#,#"));
47+
}
4948
}

0 commit comments

Comments
 (0)