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.
【题目分析】
给定一个三角,三角的结构和题目中给出的例子相同,找出从三角的顶部到底部的一条路径,使得这条路径经过的元素之和最小。每一步只能移动到下一行中和当前元素相邻的位置。
【思路】
1. triangle元素改变的方法
既然是从上往下移动,我们可以把上一层的元素的值加到下一层的相邻元素上,如果下一层某个元素在上一层中有两个相邻的元素,那个就把这两个元素中较小的那个加到下一层元素上。过程如下:
--->或者
从最后一行的值中我们可以选出最小的那个值,当然这个过程也可以反着进行,从最后一行向上加,上一层元素从它相邻的两个下层元素中选择较小的那个加到它本身。
2. triangle元素不改变的方法
这个方法的思路与上个方法是相同的,只不过这个方法不会改变三角中的元素,而是维持一个数组来存储这个改变的过程。例如从下往上的遍历过程,先把最后一行赋值给数组,从数组相邻元素中选取较小的那个加上这两个元素在上一层的共同相邻元素,这个新值依旧存储在数组中。这时空间复杂度为O(n)。
【java代码1】从上往下遍历,triangle元素改变
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0) return 0;
int triszie = triangle.size(); List<Integer> clist = triangle.get(0);
for(int i = 0; i < triszie - 1; i++){
List<Integer> nlist = triangle.get(i+1);
nlist.set(0, clist.get(0) + nlist.get(0));
for(int j = 1; j <= i; j++){
int value = Math.min(clist.get(j), clist.get(j-1)) + nlist.get(j);
nlist.set(j, value);
}
nlist.set(i+1, clist.get(i) + nlist.get(i+1));
clist = nlist;
} int min = clist.get(0);
for(int i = 1; i < clist.size(); i++){
min = Math.min(min, clist.get(i));
}
return min;
}
}
【java代码2】从下往上,triangle元素不改变
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0) return 0;
int triszie = triangle.size();
int[] dp = new int[triszie]; for(int i = triszie - 1; i >= 0; i--){
for(int j = 0; j <= i; j++){
if(i == triszie - 1) dp[j] = triangle.get(i).get(j);
else dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
LeetCode OJ 120. Triangle的更多相关文章
-
【LeetCode】120. Triangle 解题报告(Python)
[LeetCode]120. Triangle 解题报告(Python) 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 题目地址htt ...
-
【LeetCode OJ】Triangle
Problem Link: http://oj.leetcode.com/problems/triangle/ Let R[][] be a 2D array where R[i][j] (j < ...
-
【一天一道LeetCode】#120. Triangle
一天一道LeetCode 本系列文章已全部上传至我的github,地址:ZeeCoder's Github 欢迎大家关注我的新浪微博,我的新浪微博 欢迎转载,转载请注明出处 (一)题目 Given a ...
-
【LeetCode】120 - Triangle
原题:Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen ...
-
[leetcode DP]120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...
-
【LeetCode】120. Triangle (3 solutions)
Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to a ...
-
LeetCode OJ:Triangle(三角形)
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...
-
leetcode 118. Pascal&#39;s Triangle 、119. Pascal&#39;s Triangle II 、120. Triangle
118. Pascal's Triangle 第一种解法:比较麻烦 https://leetcode.com/problems/pascals-triangle/discuss/166279/cpp- ...
-
[LeetCode]题解(python):120 Triangle
题目来源 https://leetcode.com/problems/triangle/ Given a triangle, find the minimum path sum from top to ...
随机推荐
-
自定义从Azure下载回来的远程桌面连接(.rdp)文件,使其提供更多丰富功能
通常情况下,我们使用Azure的时候微软会为用户提供可连接管理虚拟机的远程桌面服务,并且支持文件实例的保存,对于Windows 系统来说,微软提供的链接文件实例就是.rdp文件. 获得.rdp文件 打 ...
-
100. Same Tree
[题目] Given two binary trees, write a function to check if they are equal or not. Two binary trees ar ...
-
JAVA中日期处理
一.日期和long类型数据的相互转换 public class Hello { public static void main(String[] args) throws Exception { // ...
-
MYSQL的存储引擎一般只要哪些?
根据个人个人见解: MySQL的存储引擎(构成.安全.锁) Myisam:数据操作快速的一种引擎,支持全文检索.文件保存在数据库名称为目录名的 目录中,有3个文件,分别是表定义文件(.frm).数据文 ...
-
IAR编译信息分析
1.怎么设置可以查看单片的内存(消耗)使用状况? IAR的菜单栏 -->Tools -->IDE Options -->Messages -->Show build messa ...
-
c# sql连接数据库
using System.Data.SqlClient; private static string connectionString ="Data Source=.\\HS;Initial ...
-
Django框架学习-Model进阶用法
Model进阶用法 回顾 访问外键 访问多对多关系 更改数据库结构 当处理数据库结构改变时,需要注意到几点: 增加字段 首先在开发环境中: 再到产品环境中: 删除字段 删除多对多字段 删除model ...
-
Jmeter(三)_配置元件
HTTP Cookie Manager 用来存储浏览器产生的用户信息 Clear Cookies each Iteration:每次迭代请求,清空cookies,GUI中定义的任何cookie都不会被 ...
-
python importlib动态导入模块
一般而言,当我们需要某些功能的模块时(无论是内置模块或自定义功能的模块),可以通过import module 或者 from * import module的方式导入,这属于静态导入,很容易理解. 而 ...
-
esayui扩展验证方法
下面是关于平时中积累的esayui扩展验证方法仅作记录: /**************************************************************** ...