【LeetCode-面试算法经典-Java实现】【120-Triangle(三角形)】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode-面试算法经典-Java实现】【120-Triangle(三角形)】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2013字,纯文字阅读大概需要3分钟。
内容图文
【120-Triangle(三角形)】
【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】
原题
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.
题目大意
给定一个三角形,找出从顶究竟的最小路径和,每一步能够从上一行移动到下一行相邻的数字
解题思路
递推方程:
f(0,0)=a[0][0]
f(i,0)=a[i][0]+f(i-1,0) (i>0)
f(i,i)=a[i][i]+f(i-1,i-1)(i>0)
f(i,j)=a[i][j]+MIN(f(i-1,j),f(i-1,j-1))(0
代码实现
算法实现类
import java.util.List;
publicclass Solution {
publicintminimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() < 1) {
return0;
}
// 创建数组的第二维度int[][] minSum = newint[triangle.size()][];
// 创建数组的第一维度for (int i = 0; i < minSum.length; i++) {
minSum[i] = newint[i + 1];
}
// 设置第一行
minSum[0][0] = triangle.get(0).get(0);
// 设置其他行for (int i = 1; i < minSum.length; i++) {
List<Integer> line = triangle.get(i);
for (int j = 0; j < minSum[i].length; j++) {
if (j == 0) {
minSum[i][0] = line.get(0) + minSum[i - 1][0];
} elseif (i == j) {
minSum[i][j] = line.get(j) + minSum[i - 1][j - 1];
} elseif (j < i) {
minSum[i][j] = line.get(j) + Math.min(minSum[i - 1][j], minSum[i - 1][j - 1]);
}
}
}
//找最后一行的最小值就是所求的解int min = minSum[minSum.length - 1][0];
int length = minSum[minSum.length - 1].length;
for (int i = 1; i < length; i++) {
if (min > minSum[length - 1][i]) {
min = minSum[length - 1][i];
}
}
return min;
}
}
评測结果
点击图片。鼠标不释放。拖动一段位置。释放后在新的窗体中查看完整图片。
特别说明
欢迎转载。转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47651229】
原文:http://www.cnblogs.com/mfmdaoyou/p/6895566.html
内容总结
以上是互联网集市为您收集整理的【LeetCode-面试算法经典-Java实现】【120-Triangle(三角形)】全部内容,希望文章能够帮你解决【LeetCode-面试算法经典-Java实现】【120-Triangle(三角形)】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。