1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle.size() == 0 || triangle.get(0).size() == 0) {
return 0;
}
Deque<Pair<Integer, Integer>> indexQ = new ArrayDeque<>();
indexQ.offer(new Pair(0, triangle.get(0).get(0)));
int level = 0;
for (level = 0; level < triangle.size() - 1; level++) {
int size = indexQ.size();
for (int i = 0; i < size; i++) {
Pair<Integer, Integer> currPair = indexQ.poll();
int currIndex = currPair.getKey();
int sumSoFar = currPair.getValue();
if (i > 0) {
Pair<Integer, Integer> previousPair = indexQ.peekLast();
if (sumSoFar + triangle.get(level + 1).get(currIndex) < previousPair.getValue()) {
indexQ.pollLast();
indexQ.offer(new Pair(currIndex, sumSoFar + triangle.get(level + 1).get(currIndex)));
}
} else {
indexQ.offer(new Pair(currIndex, sumSoFar + triangle.get(level + 1).get(currIndex)));
}
indexQ.offer(new Pair(currIndex + 1, sumSoFar + triangle.get(level + 1).get(currIndex + 1)));
}
}
int min = Integer.MAX_VALUE;
while (!indexQ.isEmpty()) {
min = Math.min(min, indexQ.poll().getValue());
}
return min;
}
}
|
最正常的brute force, 也就是BFS. 但是要优化一下, 在遍历每一行, 添加下一行的candidates的时候, 除了最左边的数字, 每个数字添加的左邻居都会和之前一个数字添加的右邻居重合. 此时可以进行一个判断, 如果当前添加这个左邻居得到的sum比之前添加的右邻居的sum要小, 那就把之前添加的poll出来, 改为现在添加的. 如果比之前大, 那现在就没必要添加了. 这样每个位置只会添加一次.
时间复杂度: O(n ^ 2) 因为把triangle每一个位置都遍历了.
空间复杂度: O(n) 每次只是装着一层, 然后添加下一层. 最多也就是n.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for (int i = triangle.size() - 2; i >= 0; i--) {
List<Integer> currRow = triangle.get(i);
List<Integer> nextRow = triangle.get(i + 1);
for (int j = 0; j < currRow.size(); j++) {
currRow.set(j, Math.min(nextRow.get(j), nextRow.get(j + 1)) + currRow.get(j));
}
}
return triangle.get(0).get(0);
}
}
|
从底部到上往上爬. 看哪个路到顶部最小.
时间复杂度: O(n^2) 因为要遍历每个位置.
空间复杂度: O(1)
