首页 > 代码库 > leetcode--Triangle
leetcode--Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3]]
The minimum path sum from top to bottom is 11
(i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
public class Solution { /**Top-down method. Since only O(n) extra memory is allowed, we use a deque to save the intermediate result. * @author Averill Zheng * @version 2014-06-23 * @since JDK 1.7 */ public int minimumTotal(List<List<Integer>> triangle) { int min = Integer.MAX_VALUE; int length = triangle.size(); if(length == 0) return 0; else if(length == 1) return triangle.get(0).get(0); else { Queue<Integer> sums = new LinkedList<Integer>(); sums.add(triangle.get(0).get(0)); for(int i = 1; i < length; ++i){ List<Integer> aList = triangle.get(i); int equalIndex = sums.poll(); sums.add(equalIndex + aList.get(i)); int smallerIndex = (i > 1) ? sums.peek(): Math.abs(equalIndex); for(int j = i - 1; j > 0; --j){ sums.add(Math.min(smallerIndex + aList.get(j), equalIndex + aList.get(j))); equalIndex = sums.poll(); smallerIndex = sums.peek(); } sums.add(equalIndex + aList.get(0)); } while(sums.peek() != null){ min = Math.min(min, sums.poll()); } } return min; }}
method 2: bottom-up method
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { Queue<Integer> sums = new LinkedList<Integer>(); int length = triangle.size(); if(length == 0) return 0; else if(length == 1) return triangle.get(0).get(0); else { List<Integer> lastList = triangle.get(length - 1); for(int i = 0; i < length; ++i) sums.add(lastList.get(i)); for(int i = length - 2; i > -1; --i){ List<Integer> currentList = triangle.get(i); for(int j = 0; j < i + 1; ++j){ int equalIndex = sums.poll(); int largerIndex = sums.peek(); sums.add(currentList.get(j) + Math.min(equalIndex, largerIndex)); } sums.poll(); } } return sums.peek(); }}
method 3. bottom-up , and use List<Integer> as the data structure to save the intermediate result.
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { int length = triangle.size(); List<Integer> pathSum = new ArrayList<Integer>(); if(length == 0) return 0; pathSum.addAll(triangle.get(length - 1)); for(int i = length - 2; i > -1; --i){ List<Integer> aList = triangle.get(i); for(int j = 0; j < i + 1; ++j) pathSum.set(j, Math.min(pathSum.get(j), pathSum.get(j + 1))+ aList.get(j)); } return pathSum.get(0); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。