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:
这次题目一开始想偏了,觉得应该用最短路径算法来做。后来发现没有这么复杂。
首先,到每一层的最短距离,通过简单的算法,我们是无法确定的。
但是,我们可以确定的是,到每一个结点的最短距离。这个是很容易确定的。类似于上面那道题目,设置一个数组,不断刷新就行。
然后出现一个问题。该如何遍历上一层呢?
我一开始设置了两个数组,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));
}
}
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));
}
}
这道题木我没有做出来,因为,我想复杂了。
我觉得,既然要找出最小值,就得找出他们的路径,会很复杂,需要全部计算,而这个很难用代码实现,而且可能违背了简洁的思想。
但关键在于,题目只要求我们求出最小值,而不需要把路径找出来。
那么就可以只计算到每个结点的最短距离,其实就是全部算一遍,然后在最后,找出那个数组的最小值。
同样的是从右到左扫描。
第一段代码,我用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