Skip to content

Commit f78e6d9

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0120. Triangle
1 parent 4a85274 commit f78e6d9

File tree

8 files changed

+239
-37
lines changed

8 files changed

+239
-37
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,7 @@
186186
- [杨辉三角](./solution/0100-0199/0118.Pascal%27s%20Triangle/README.md)
187187
- [杨辉三角 II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README.md)
188188
- [下降路径最小和](./solution/0900-0999/0931.Minimum%20Falling%20Path%20Sum/README.md)
189+
- [三角形最小路径和](./solution/0100-0199/0120.Triangle/README.md)
189190
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
190191
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
191192
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -180,6 +180,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
180180
- [Pascal's Triangle](./solution/0100-0199/0118.Pascal%27s%20Triangle/README_EN.md)
181181
- [Pascal's Triangle II](./solution/0100-0199/0119.Pascal%27s%20Triangle%20II/README_EN.md)
182182
- [Minimum Falling Path Sum](./solution/0900-0999/0931.Minimum%20Falling%20Path%20Sum/README_EN.md)
183+
- [Triangle](./solution/0100-0199/0120.Triangle/README_EN.md)
183184
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
184185
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
185186
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)

‎solution/0100-0199/0120.Triangle/README.md

Lines changed: 87 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,22 +56,108 @@
5656

5757
<!-- 这里可写通用的实现逻辑 -->
5858

59+
动态规划。
60+
5961
<!-- tabs:start -->
6062

6163
### **Python3**
6264

6365
<!-- 这里可写当前语言的特殊实现逻辑 -->
6466

6567
```python
66-
68+
class Solution:
69+
def minimumTotal(self, triangle: List[List[int]]) -> int:
70+
n = len(triangle)
71+
for i in range(1, n):
72+
for j in range(i + 1):
73+
mi = float('inf')
74+
if j > 0:
75+
mi = min(mi, triangle[i - 1][j - 1])
76+
if j < i:
77+
mi = min(mi, triangle[i - 1][j])
78+
triangle[i][j] += mi
79+
return min(triangle[n - 1])
6780
```
6881

6982
### **Java**
7083

7184
<!-- 这里可写当前语言的特殊实现逻辑 -->
7285

7386
```java
87+
class Solution {
88+
public int minimumTotal(List<List<Integer>> triangle) {
89+
int n = triangle.size();
90+
for (int i = 1; i < n; ++i) {
91+
for (int j = 0; j < i + 1; ++j) {
92+
int mi = Integer.MAX_VALUE;
93+
if (j > 0) {
94+
mi = Math.min(mi, triangle.get(i - 1).get(j - 1));
95+
}
96+
if (j < i) {
97+
mi = Math.min(mi, triangle.get(i - 1).get(j));
98+
}
99+
triangle.get(i).set(j, triangle.get(i).get(j) + mi);
100+
}
101+
}
102+
int res = Integer.MAX_VALUE;
103+
for (int val : triangle.get(n - 1)) {
104+
res = Math.min(res, val);
105+
}
106+
return res;
107+
}
108+
}
109+
```
110+
111+
### **C++**
112+
113+
```cpp
114+
class Solution {
115+
public:
116+
int minimumTotal(vector<vector<int>>& triangle) {
117+
int n = triangle.size();
118+
for (int i = 1; i < n; ++i) {
119+
for (int j = 0; j < i + 1; ++j) {
120+
int mi = INT_MAX;
121+
if (j > 0) mi = min(mi, triangle[i - 1][j - 1]);
122+
if (j < i) mi = min(mi, triangle[i - 1][j]);
123+
triangle[i][j] += mi;
124+
}
125+
}
126+
int res = INT_MAX;
127+
for (int& val : triangle[n - 1]) {
128+
res = min(res, val);
129+
}
130+
return res;
131+
}
132+
};
133+
```
74134
135+
### **Go**
136+
137+
```go
138+
func minimumTotal(triangle [][]int) int {
139+
n := len(triangle)
140+
for i := 1; i < n; i++ {
141+
for j := 0; j < i+1; j++ {
142+
mi := 2000000
143+
if j > 0 && mi > triangle[i-1][j-1] {
144+
mi = triangle[i-1][j-1]
145+
}
146+
if j < i && mi > triangle[i-1][j] {
147+
mi = triangle[i-1][j]
148+
}
149+
triangle[i][j] += mi
150+
}
151+
}
152+
153+
res := 2000000
154+
for j := 0; j < n; j++ {
155+
if res > triangle[n-1][j] {
156+
res = triangle[n-1][j]
157+
}
158+
}
159+
return res
160+
}
75161
```
76162

77163
### **...**

‎solution/0100-0199/0120.Triangle/README_EN.md

Lines changed: 87 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,18 +44,104 @@ The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above)
4444

4545
## Solutions
4646

47+
Dynamic programming.
48+
4749
<!-- tabs:start -->
4850

4951
### **Python3**
5052

5153
```python
52-
54+
class Solution:
55+
def minimumTotal(self, triangle: List[List[int]]) -> int:
56+
n = len(triangle)
57+
for i in range(1, n):
58+
for j in range(i + 1):
59+
mi = float('inf')
60+
if j > 0:
61+
mi = min(mi, triangle[i - 1][j - 1])
62+
if j < i:
63+
mi = min(mi, triangle[i - 1][j])
64+
triangle[i][j] += mi
65+
return min(triangle[n - 1])
5366
```
5467

5568
### **Java**
5669

5770
```java
71+
class Solution {
72+
public int minimumTotal(List<List<Integer>> triangle) {
73+
int n = triangle.size();
74+
for (int i = 1; i < n; ++i) {
75+
for (int j = 0; j < i + 1; ++j) {
76+
int mi = Integer.MAX_VALUE;
77+
if (j > 0) {
78+
mi = Math.min(mi, triangle.get(i - 1).get(j - 1));
79+
}
80+
if (j < i) {
81+
mi = Math.min(mi, triangle.get(i - 1).get(j));
82+
}
83+
triangle.get(i).set(j, triangle.get(i).get(j) + mi);
84+
}
85+
}
86+
int res = Integer.MAX_VALUE;
87+
for (int val : triangle.get(n - 1)) {
88+
res = Math.min(res, val);
89+
}
90+
return res;
91+
}
92+
}
93+
```
94+
95+
### **C++**
96+
97+
```cpp
98+
class Solution {
99+
public:
100+
int minimumTotal(vector<vector<int>>& triangle) {
101+
int n = triangle.size();
102+
for (int i = 1; i < n; ++i) {
103+
for (int j = 0; j < i + 1; ++j) {
104+
int mi = INT_MAX;
105+
if (j > 0) mi = min(mi, triangle[i - 1][j - 1]);
106+
if (j < i) mi = min(mi, triangle[i - 1][j]);
107+
triangle[i][j] += mi;
108+
}
109+
}
110+
int res = INT_MAX;
111+
for (int& val : triangle[n - 1]) {
112+
res = min(res, val);
113+
}
114+
return res;
115+
}
116+
};
117+
```
58118
119+
### **Go**
120+
121+
```go
122+
func minimumTotal(triangle [][]int) int {
123+
n := len(triangle)
124+
for i := 1; i < n; i++ {
125+
for j := 0; j < i+1; j++ {
126+
mi := 2000000
127+
if j > 0 && mi > triangle[i-1][j-1] {
128+
mi = triangle[i-1][j-1]
129+
}
130+
if j < i && mi > triangle[i-1][j] {
131+
mi = triangle[i-1][j]
132+
}
133+
triangle[i][j] += mi
134+
}
135+
}
136+
137+
res := 2000000
138+
for j := 0; j < n; j++ {
139+
if res > triangle[n-1][j] {
140+
res = triangle[n-1][j]
141+
}
142+
}
143+
return res
144+
}
59145
```
60146

61147
### **...**

‎solution/0100-0199/0120.Triangle/Solution.cpp

Lines changed: 12 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,19 @@
11
class Solution {
22
public:
33
int minimumTotal(vector<vector<int>>& triangle) {
4-
size_t rowNum = triangle.size();
5-
6-
//特殊值处理
7-
if(rowNum == 0)return 0;
8-
if(rowNum == 1){
9-
if(triangle[0].empty())return 0;
10-
else return triangle[0][0];
11-
}
12-
13-
for(int i = 1;i<rowNum;i++){
14-
for(int j = i;j>=0;j--){
15-
//边界处理
16-
if(j == 0){triangle[i][j] = triangle[i][j] + triangle[i-1][j];continue;}
17-
if(j == i){triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];continue;}
18-
19-
//一般处理
20-
triangle[i][j] = triangle[i][j] + min(triangle[i-1][j],triangle[i-1][j-1]);
4+
int n = triangle.size();
5+
for (int i = 1; i < n; ++i) {
6+
for (int j = 0; j < i + 1; ++j) {
7+
int mi = INT_MAX;
8+
if (j > 0) mi = min(mi, triangle[i - 1][j - 1]);
9+
if (j < i) mi = min(mi, triangle[i - 1][j]);
10+
triangle[i][j] += mi;
2111
}
2212
}
23-
24-
int ans = INT_MAX;
25-
for(auto v : triangle[rowNum-1]){
26-
if(ans > v)ans = v;
27-
}
28-
return ans;
13+
int res = INT_MAX;
14+
for (int& val : triangle[n - 1]) {
15+
res = min(res, val);
16+
}
17+
return res;
2918
}
3019
};

‎solution/0100-0199/0120.Triangle/Solution.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
func minimumTotal(triangle [][]int) int {
2+
n := len(triangle)
3+
for i := 1; i < n; i++ {
4+
for j := 0; j < i+1; j++ {
5+
mi := 2000000
6+
if j > 0 && mi > triangle[i-1][j-1] {
7+
mi = triangle[i-1][j-1]
8+
}
9+
if j < i && mi > triangle[i-1][j] {
10+
mi = triangle[i-1][j]
11+
}
12+
triangle[i][j] += mi
13+
}
14+
}
15+
16+
res := 2000000
17+
for j := 0; j < n; j++ {
18+
if res > triangle[n-1][j] {
19+
res = triangle[n-1][j]
20+
}
21+
}
22+
return res
23+
}

‎solution/0100-0199/0120.Triangle/Solution.java

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,22 @@
11
class Solution {
2-
private int[][] cache = null;
32
public int minimumTotal(List<List<Integer>> triangle) {
43
int n = triangle.size();
5-
cache = new int[n][triangle.get(n - 1).size()];
6-
for (int[] row : cache) Arrays.fill(row, -1);
7-
return dfs(triangle,0,0);
8-
}
9-
private int dfs(List<List<Integer>> triangle, int row, int col) {
10-
if (row == triangle.size()) return 0;
11-
if (cache[row][col] != -1) return cache[row][col];
12-
int l = dfs(triangle,row+1,col);
13-
int r = dfs(triangle,row+1,col+1);
14-
int res = Math.min(l,r)+triangle.get(row).get(col);
15-
cache[row][col] = res;
4+
for (int i = 1; i < n; ++i) {
5+
for (int j = 0; j < i + 1; ++j) {
6+
int mi = Integer.MAX_VALUE;
7+
if (j > 0) {
8+
mi = Math.min(mi, triangle.get(i - 1).get(j - 1));
9+
}
10+
if (j < i) {
11+
mi = Math.min(mi, triangle.get(i - 1).get(j));
12+
}
13+
triangle.get(i).set(j, triangle.get(i).get(j) + mi);
14+
}
15+
}
16+
int res = Integer.MAX_VALUE;
17+
for (int val : triangle.get(n - 1)) {
18+
res = Math.min(res, val);
19+
}
1620
return res;
1721
}
1822
}

‎solution/0100-0199/0120.Triangle/Solution.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution:
2+
def minimumTotal(self, triangle: List[List[int]]) -> int:
3+
n = len(triangle)
4+
for i in range(1, n):
5+
for j in range(i + 1):
6+
mi = float('inf')
7+
if j > 0:
8+
mi = min(mi, triangle[i - 1][j - 1])
9+
if j < i:
10+
mi = min(mi, triangle[i - 1][j])
11+
triangle[i][j] += mi
12+
return min(triangle[n - 1])

0 commit comments

Comments
 (0)