首页 > 代码库 > [LeetCode]120 Triangle
[LeetCode]120 Triangle
https://oj.leetcode.com/problems/triangle/
http://blog.csdn.net/linhuanmars/article/details/23230657
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { // Solution A: // return minimumTotal_MaintainSums(triangle); // Solution B: return minimumTotal_NoExtraSpace(triangle); } ///////////////////////// // Solution B: NoExtraSpace // // Use Extra O(n) to maintain current row. // Use triangle to maintain sums. private int minimumTotal_NoExtraSpace(List<List<Integer>> triangle) { List<Integer> extra = new ArrayList<>(triangle.get(triangle.size() - 1).size()); for (int i = 1 ; i < triangle.size() ; i ++) { // Copy this row to extra memory for next iteration using. extra.clear(); for (int j : triangle.get(i)) extra.add(j); // Calculating this row, change it to sums. for (int j = 0 ; j < triangle.get(i).size() ; j ++) { int v = Math.min(val(triangle, i - 1, j - 1), val(triangle, i - 1, j)); v = v += extra.get(j); triangle.get(i).set(j, v); } } List<Integer> lastlevel = triangle.get(triangle.size() - 1); int min = Integer.MAX_VALUE; for (int i : lastlevel) { if (i < min) min = i; } return min; } ///////////////////////// // Solution A: MaintainSums // // Maintain sums in another List<List<Integer>> // private int minimumTotal_MaintainSums(List<List<Integer>> triangle) { // Assumes // Not null. // triangle.size >= 1 List<List<Integer>> sums = new ArrayList<>(); sums.add(Collections.<Integer> singletonList(triangle.get(0).get(0))); for (int i = 1 ; i < triangle.size() ; i ++) { // Level size int levelsize = i + 1; List<Integer> newSum = new ArrayList<>(levelsize); for (int j = 0 ; j < levelsize ; j ++) { int v = Math.min(val(sums, i - 1, j - 1), val(sums, i - 1, j)); v = v += triangle.get(i).get(j); newSum.add(v); } sums.add(newSum); } List<Integer> lastlevel = sums.get(sums.size() - 1); int min = Integer.MAX_VALUE; for (int i : lastlevel) { if (i < min) min = i; } return min; } private int val(List<List<Integer>> t, int row, int index) { List<Integer> level = t.get(row); if (index < 0 || index >= level.size()) return Integer.MAX_VALUE; return level.get(index); } }
[LeetCode]120 Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。