Paste_Image.png
My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0)
return 0;
if (triangle.size() == 1)
return triangle.get(0).get(0);
int[] currDis = new int[triangle.size()];
currDis[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
currDis[i] = currDis[i - 1] + triangle.get(i).get(i);
for (int j = i - 1; j > 0; j--)
currDis[j] = Math.min(currDis[j - 1], currDis[j]) + triangle.get(i).get(j);
currDis[0] = currDis[0] + triangle.get(i).get(0);
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < currDis.length; i++) {
if (min > currDis[i])
min = currDis[i];
}
return min;
}
public static void main(String[] args) {
Solution test = new Solution();
ArrayList<Integer> a0 = new ArrayList<Integer>();
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<Integer> a2 = new ArrayList<Integer>();
a0.add(-1);
a1.add(2);
a1.add(3);
a2.add(1);
a2.add(-1);
a2.add(-3);
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(a0);
result.add(a1);
result.add(a2);
System.out.println(test.minimumTotal(result));
}
}
My test result:
Paste_Image.png
这次题目一开始想偏了，觉得应该用最短路径算法来做。后来发现没有这么复杂。
首先，到每一层的最短距离，通过简单的算法，我们是无法确定的。
但是，我们可以确定的是，到每一个结点的最短距离。这个是很容易确定的。类似于上面那道题目，设置一个数组，不断刷新就行。
然后出现一个问题。该如何遍历上一层呢？
我一开始设置了两个数组，pastDis[] and currDis[]
分别用来记录上一层和这一层的数据，然后不断刷新。
后来查看代码发现不需要这么复杂，直接一个数组就可以完工。并且可以解决因为覆盖原数据导致的错误问题。方法就是从右往左遍历。然后可以避免使用了已被覆盖的数据。
差不多就这样啦。
**
总结： Array
**
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0)
return 0;
int[] ret = new int[triangle.size()]; // record data
/** scan from right to left, store minimum value to every element from upper to down */
ret[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
for (int j = triangle.get(i).size() - 1; j >= 0; j--) {
if (j == triangle.get(i).size() - 1)
ret[j] = triangle.get(i).get(j) + ret[j - 1];
else if (j == 0)
ret[j] = triangle.get(i).get(j) + ret[j];
else
ret[j] = triangle.get(i).get(j) + Math.min(ret[j - 1], ret[j]);
}
}
/** find the minimum element in the ret array which means the minimum sum */
Arrays.sort(ret);
return ret[0];
}
public static void main(String[] args) {
Solution test = new Solution();
ArrayList<Integer> a0 = new ArrayList<Integer>();
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<Integer> a2 = new ArrayList<Integer>();
ArrayList<Integer> a3 = new ArrayList<Integer>();
a0.add(2);
a1.add(3);
a1.add(4);
a2.add(6);
a2.add(5);
a2.add(7);
a3.add(4);
a3.add(1);
a3.add(8);
a3.add(3);
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(a0);
result.add(a1);
result.add(a2);
result.add(a3);
System.out.println(test.minimumTotal(result));
}
}
Screenshot from 2016-01-11 11:41:31.png
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0)
return 0;
int[] ret = new int[triangle.size()]; // record data
/** scan from right to left, store minimum value to every element from upper to down */
ret[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
int size = i + 1;
ret[size - 1] = triangle.get(i).get(size - 1) + ret[size - 2]; // for right end
for (int j = size - 2; j >= 1; j--) {
ret[j] = triangle.get(i).get(j) + Math.min(ret[j - 1], ret[j]);
}
ret[0] = triangle.get(i).get(0) + ret[0]; // for left end
}
/** find the minimum element in the ret array which means the minimum sum */
Arrays.sort(ret);
return ret[0];
}
public static void main(String[] args) {
Solution test = new Solution();
ArrayList<Integer> a0 = new ArrayList<Integer>();
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<Integer> a2 = new ArrayList<Integer>();
ArrayList<Integer> a3 = new ArrayList<Integer>();
a0.add(2);
a1.add(3);
a1.add(4);
a2.add(6);
a2.add(5);
a2.add(7);
a3.add(4);
a3.add(1);
a3.add(8);
a3.add(3);
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(a0);
result.add(a1);
result.add(a2);
result.add(a3);
System.out.println(test.minimumTotal(result));
}
}
Screenshot from 2016-01-11 15:14:51.png
这道题木我没有做出来，因为，我想复杂了。
我觉得，既然要找出最小值，就得找出他们的路径，会很复杂，需要全部计算，而这个很难用代码实现，而且可能违背了简洁的思想。
但关键在于，题目只要求我们求出最小值，而不需要把路径找出来。
那么就可以只计算到每个结点的最短距离，其实就是全部算一遍，然后在最后，找出那个数组的最小值。
同样的是从右到左扫描。
第一段代码，我用if else 实现，来处理corner case。时间为7ms
第二段代码，我想办法取消掉了if else，少了判断，时间一下短了， 变成了4ms,效率提升了近100%.
最近太懒惰了，
苏秦遭受了那么大的挫折，最后还是站了起来，即使毫无希望，依然坚持自己。
很令人感动。虽然可能只是大秦帝国这本小说戏剧描绘的。
我不能放弃！
还有十天。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int[] level = new int[triangle.size()];
level[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
List<Integer> list = triangle.get(i);
for (int j = list.size() - 1; j >= 0; j--) {
if (j == list.size() - 1) {
level[j] = list.get(list.size() - 1) + level[j - 1];
}
else if (j == 0) {
level[j] = list.get(0) + level[0];
}
else {
level[j] = Math.min(level[j - 1], level[j]) + list.get(j);
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < level.length; i++) {
min = Math.min(min, level[i]);
}
return min;
}
}
这一遍做，终于做出来了。因为我一直记得这道题目，我以前的错误在于，想找出路径。其实只用找到最小值，不用找到路径。
Anyway, Good luck, Richardo! --- 08/05/2016
