8000 refactor 120 · tobeexpert/Leetcode@8829017 · GitHub
[go: up one dir, main page]
Skip to cont 8000 ent

Commit 8829017

Browse files
fishercoder1534fishercoder1534
committed
refactor 120
1 parent 95c1494 commit 8829017

File tree

2 files changed

+47
-27
lines changed

2 files changed

+47
-27
lines changed

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

Lines changed: 19 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,11 @@
11
package com.fishercoder.solutions;
22

3-
import java.util.ArrayList;
4-
import java.util.Arrays;
53
import java.util.List;
64

7-
/**Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
5+
/**
6+
* 120. Triangle
7+
8+
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
89
910
For example, given the following triangle
1011
[
@@ -17,31 +18,22 @@
1718
1819
Note:
1920
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.*/
20-
public class _120 {
2121

22-
public static int minimumTotal(List<List<Integer>> triangle) {
23-
/**https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle, @stellari has a very excellent explanation.
24-
* Basically, we use the bottom-up approach, starting from the bottom row of this triangle, and we only need to store the shortest path of each node
25-
* from its last row, and keep overwriting it until we reach the top.*/
26-
int n = triangle.size();
27-
List<Integer> cache = triangle.get(n - 1);
28-
29-
for (int layer = n - 2; layer >= 0; layer--) {
30-
//for each layer
31-
for (int i = 0; i <= layer; i++) {
32-
//check its very node
33-
int value = Math.min(cache.get(i), cache.get(i + 1)) + triangle.get(layer).get(i);
34-
cache.set(i, value);
35-
}
22+
public class _120 {
23+
public static class Solution1 {
24+
public int minimumTotal(List<List<Integer>> triangle) {
25+
int n = triangle.size();
26+
List<Integer> cache = triangle.get(n - 1);
27+
28+
for (int layer = n - 2; layer >= 0; layer--) {
29+
//for each layer
30+
for (int i = 0; i <= layer; i++) {
31+
//check its very node
32+
int value = Math.min(cache.get(i), cache.get(i + 1)) + triangle.get(layer).get(i);
33+
cache.set(i, value);
3634
}
37-
return cache.get(0);
35+
}
36+
return cache.get(0);
3837
}
39-
40-
public static void main(String... strings) {
41-
List<List<Integer>> triangle = new ArrayList();
42-
triangle.add(Arrays.asList(1));
43-
triangle.add(Arrays.asList(2, 3));
44-
System.out.println(minimumTotal(triangle));
45-
}
46-
38+
}
4739
}

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

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._120;
4+
import java.util.ArrayList;
5+
import java.util.Arrays;
6+
import java.util.List;
7+
import org.junit.BeforeClass;
8+
import org.junit.Test;
9+
10+
import static junit.framework.Assert.assertEquals;
11+
12+
public class _120Test {
13+
private static _120.Solution1 solution1;
14+
private static List<List<Integer>> triangle;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
solution1 = new _120.Solution1();
19+
}
20+
21+
@Test
22+
public void test1() {
23+
triangle = new ArrayList();
24+
triangle.add(Arrays.asList(1));
25+
triangle.add(Arrays.asList(2, 3));
26+
assertEquals(3, solution1.minimumTotal(triangle));
27+
}
28+
}

0 commit comments

Comments
 (0)
0