Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit298dfb2

Browse files
add accepted solution for 1104 and tests
1 parent6ae4db4 commit298dfb2

File tree

2 files changed

+74
-1
lines changed

2 files changed

+74
-1
lines changed

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

Lines changed: 54 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,11 @@
11
packagecom.fishercoder.solutions;
22

33
importcom.fishercoder.common.classes.TreeNode;
4+
importcom.fishercoder.common.utils.CommonUtils;
45
importcom.fishercoder.common.utils.TreeUtils;
56

6-
importjava.lang.reflect.Array;
77
importjava.util.ArrayList;
8+
importjava.util.Arrays;
89
importjava.util.Collections;
910
importjava.util.Deque;
1011
importjava.util.LinkedList;
@@ -36,6 +37,7 @@ public static class Solution1 {
3637
/**This brute force solution is correct but results in TLE on LeetCode.*/
3738
publicList<Integer>pathInZigZagTree(intlabel) {
3839
Deque<Integer>deque =buildZigZagOrderList(label);
40+
CommonUtils.printDeque(deque);
3941
TreeNoderoot =buildZigZagOrderTree(deque);
4042
TreeUtils.printBinaryTree(root);
4143
returndfs(root,label,newArrayList<>());
@@ -97,4 +99,55 @@ private Deque<Integer> buildZigZagOrderList(int label) {
9799
returndeque;
98100
}
99101
}
102+
103+
publicstaticclassSolution2 {
104+
/**We'll directly compute the index of its parent, it'll be much faster this way.*/
105+
publicList<Integer>pathInZigZagTree(intlabel) {
106+
List<List<Integer>>lists =buildZigZagOrderList(label);
107+
CommonUtils.printListList(lists);
108+
List<Integer>result =newArrayList<>();
109+
intindex =findIndex(lists.get(lists.size() -1),label);
110+
result.add(label);
111+
for (inti =lists.size() -2;i >=0;i--) {
112+
index /=2;
113+
result.add(lists.get(i).get(index));
114+
}
115+
Collections.sort(result);
116+
returnresult;
117+
}
118+
119+
privateintfindIndex(List<Integer>level,intlabel) {
120+
for (inti =0;i <level.size();i++) {
121+
if (level.get(i) ==label) {
122+
returni;
123+
}
124+
}
125+
return -1;
126+
}
127+
128+
privateList<List<Integer>>buildZigZagOrderList(intlabel) {
129+
List<List<Integer>>lists =newArrayList<>();
130+
intnum =1;
131+
intlevel =2;
132+
lists.add(Arrays.asList(num));
133+
if (label ==1) {
134+
returnlists;
135+
}
136+
List<Integer>newLevel =newArrayList<>();
137+
do {
138+
newLevel.clear();
139+
num++;
140+
for (;num <Math.pow(2,level);num++) {
141+
newLevel.add(num);
142+
}
143+
num--;
144+
if (level %2 ==0) {
145+
Collections.reverse(newLevel);
146+
}
147+
lists.add(newArrayList<>(newLevel));
148+
level++;
149+
}while (newLevel.get(0) <label &&newLevel.get(newLevel.size() -1) <label);
150+
returnlists;
151+
}
152+
}
100153
}

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

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,11 +12,13 @@
1212

1313
publicclass_1104Test {
1414
privatestatic_1104.Solution1solution1;
15+
privatestatic_1104.Solution2solution2;
1516
privatestaticList<Integer>expected;
1617

1718
@BeforeClass
1819
publicstaticvoidsetup() {
1920
solution1 =new_1104.Solution1();
21+
solution2 =new_1104.Solution2();
2022
}
2123

2224
@Test
@@ -81,4 +83,22 @@ public void test9() {
8183
assertEquals(expected,solution1.pathInZigZagTree(500000));
8284
}
8385

86+
@Test
87+
publicvoidtest10() {
88+
expected =Arrays.asList(1);
89+
assertEquals(expected,solution1.pathInZigZagTree(1));
90+
}
91+
92+
@Test
93+
publicvoidtest11() {
94+
expected =Arrays.asList(1,3,4,14);
95+
assertEquals(expected,solution2.pathInZigZagTree(14));
96+
}
97+
98+
@Test
99+
publicvoidtest12() {
100+
expected =Arrays.asList(1);
101+
assertEquals(expected,solution2.pathInZigZagTree(1));
102+
}
103+
84104
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp