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

Commit546c252

Browse files
refactor 666
1 parentab54de8 commit546c252

File tree

2 files changed

+52
-6
lines changed

2 files changed

+52
-6
lines changed

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

Lines changed: 40 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,9 @@
22

33
importcom.fishercoder.common.classes.TreeNode;
44

5+
importjava.util.HashMap;
6+
importjava.util.Map;
7+
58
/**
69
* 666. Path Sum IV
710
* If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.
@@ -16,7 +19,7 @@
1619
The units digit represents the value V of this node, 0 <= V <= 9.
1720
1821
Given a list of ascending three-digits integers representing a binary with the depth smaller than 5.
19-
You need to return thesum of all paths from the root towards the leaves.
22+
You need to return thetotalSum of all paths from the root towards the leaves.
2023
2124
Example 1:
2225
@@ -28,7 +31,7 @@
2831
/ \
2932
5 1
3033
31-
The pathsum is (3 + 5) + (3 + 1) = 12.
34+
The pathtotalSum is (3 + 5) + (3 + 1) = 12.
3235
3336
Example 2:
3437
@@ -40,7 +43,7 @@ The path sum is (3 + 5) + (3 + 1) = 12.
4043
\
4144
1
4245
43-
The pathsum is (3 + 1) = 4.
46+
The pathtotalSum is (3 + 1) = 4.
4447
4548
*/
4649
publicclass_666 {
@@ -125,4 +128,38 @@ private TreeNode constructTree(int[] nums) {
125128
returnroot;
126129
}
127130
}
131+
132+
publicstaticclassSolution2 {
133+
publicinttotalSum =0;
134+
135+
publicintpathSum(int[]nums) {
136+
Map<Integer,Integer>map =newHashMap<>();
137+
for (inti =0;i <nums.length;i++) {
138+
intkey =nums[i] /10;
139+
intvalue =nums[i] %10;
140+
map.put(key,value);
141+
}
142+
dfs(nums[0] /10,0,map);
143+
returntotalSum;
144+
}
145+
146+
privatevoiddfs(intnode,intpreSum,Map<Integer,Integer>map) {
147+
intlevel =node /10;
148+
intpos =node %10;
149+
intleftChild = (level +1) *10 +pos *2 -1;
150+
intrightChild = (level +1) *10 +pos *2;
151+
intcurrSum =preSum +map.get(node);
152+
if (!map.containsKey(leftChild) && !map.containsKey(rightChild)) {
153+
totalSum +=currSum;
154+
return;
155+
}
156+
157+
if (map.containsKey(leftChild)) {
158+
dfs(leftChild,currSum,map);
159+
}
160+
if (map.containsKey(rightChild)) {
161+
dfs(rightChild,currSum,map);
162+
}
163+
}
164+
}
128165
}
Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,48 @@
11
packagecom.fishercoder;
22

33
importcom.fishercoder.solutions._666;
4+
importorg.junit.Before;
45
importorg.junit.BeforeClass;
56
importorg.junit.Test;
67

78
importstaticorg.junit.Assert.assertEquals;
89

910
publicclass_666Test {
1011
privatestatic_666.Solution1solution1;
12+
privatestatic_666.Solution2solution2;
1113
privatestaticint[]nums;
1214

1315
@BeforeClass
1416
publicstaticvoidsetup() {
1517
solution1 =new_666.Solution1();
18+
solution2 =new_666.Solution2();
19+
}
20+
21+
@Before
22+
publicvoidcleanUp() {
23+
solution1.totalSum =0;
24+
solution2.totalSum =0;
1625
}
1726

1827
@Test
1928
publicvoidtest1() {
2029
nums =newint[]{113,215,221};
21-
solution1.totalSum =0;
2230
assertEquals(12,solution1.pathSum(nums));
31+
assertEquals(12,solution2.pathSum(nums));
2332
}
2433

2534
@Test
2635
publicvoidtest2() {
2736
nums =newint[]{113,221};
28-
solution1.totalSum =0;
2937
assertEquals(4,solution1.pathSum(nums));
38+
assertEquals(4,solution2.pathSum(nums));
3039
}
3140

3241
@Test
3342
publicvoidtest3() {
3443
nums =newint[]{113,214,221,348,487};
35-
solution1.totalSum =0;
3644
assertEquals(26,solution1.pathSum(nums));
45+
assertEquals(26,solution2.pathSum(nums));
3746
}
3847

3948
}

0 commit comments

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